Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Changes In Branch merge-sort Excluding Merge-Ins
This is equivalent to a diff from 2869ed28 to 99e34bdc
2011-09-03
| ||
17:07 | Performance improvements to the external merge-sorter. Keep content on an in-memory linked lists rather than an ephemeral table prior to spilling to disk. Use the external merge-sorter to implement ORDER BY and GROUP BY in addition to CREATE INDEX. (check-in: 4c43e8b2 user: drh tags: trunk) | |
16:42 | Simplification and performance tweaks in vdbeSorterMerge(). (Closed-Leaf check-in: 99e34bdc user: drh tags: merge-sort) | |
14:36 | Reduce the number of VdbeRecordUnpack() calls made in vdbesort.c. (check-in: 666c2c3c user: dan tags: merge-sort) | |
2011-09-02
| ||
15:08 | Remove unused local variable. (check-in: 61bda876 user: mistachkin tags: trunk) | |
2011-09-01
| ||
15:32 | Experimental code-generator changes to utilize new opcodes for sorting. (check-in: bab2e560 user: drh tags: merge-sort) | |
2011-08-31
| ||
23:57 | Avoid using uninitialized variables after failures in the merge sort code. (check-in: 2869ed28 user: drh tags: trunk) | |
21:01 | Formerly, we enabled fdatasync() on linux only. But now we learn that fdatasync() is not supported on Android. So we disable fdatasync() on Linux too. It can be reenabled at compile-time for those who really need it. (check-in: 70b5b309 user: drh tags: trunk) | |
Changes to src/btree.c.
︙ | ︙ | |||
1730 1731 1732 1733 1734 1735 1736 | /* Only a BTREE_SINGLE database can be BTREE_UNORDERED */ assert( (flags & BTREE_UNORDERED)==0 || (flags & BTREE_SINGLE)!=0 ); /* A BTREE_SINGLE database is always a temporary and/or ephemeral */ assert( (flags & BTREE_SINGLE)==0 || isTempDb ); | < < < < < < < < < < < | 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 | /* Only a BTREE_SINGLE database can be BTREE_UNORDERED */ assert( (flags & BTREE_UNORDERED)==0 || (flags & BTREE_SINGLE)!=0 ); /* A BTREE_SINGLE database is always a temporary and/or ephemeral */ assert( (flags & BTREE_SINGLE)==0 || isTempDb ); if( db->flags & SQLITE_NoReadlock ){ flags |= BTREE_NO_READLOCK; } if( isMemdb ){ flags |= BTREE_MEMORY; } if( (vfsFlags & SQLITE_OPEN_MAIN_DB)!=0 && (isMemdb || isTempDb) ){ vfsFlags = (vfsFlags & ~SQLITE_OPEN_MAIN_DB) | SQLITE_OPEN_TEMP_DB; } p = sqlite3MallocZero(sizeof(Btree)); if( !p ){ return SQLITE_NOMEM; |
︙ | ︙ | |||
7292 7293 7294 7295 7296 7297 7298 | */ zeroPage(pPage, PTF_INTKEY|PTF_LEAF ); releasePage(pPage); } return rc; } int sqlite3BtreeDropTable(Btree *p, int iTable, int *piMoved){ | < < < < < < | < | 7281 7282 7283 7284 7285 7286 7287 7288 7289 7290 7291 7292 7293 7294 7295 7296 7297 | */ zeroPage(pPage, PTF_INTKEY|PTF_LEAF ); releasePage(pPage); } return rc; } int sqlite3BtreeDropTable(Btree *p, int iTable, int *piMoved){ int rc; sqlite3BtreeEnter(p); rc = btreeDropTable(p, iTable, piMoved); sqlite3BtreeLeave(p); return rc; } /* ** This function may only be called if the b-tree connection already |
︙ | ︙ |
Changes to src/btree.h.
︙ | ︙ | |||
57 58 59 60 61 62 63 | ** pager.h. */ #define BTREE_OMIT_JOURNAL 1 /* Do not create or use a rollback journal */ #define BTREE_NO_READLOCK 2 /* Omit readlocks on readonly files */ #define BTREE_MEMORY 4 /* This is an in-memory DB */ #define BTREE_SINGLE 8 /* The file contains at most 1 b-tree */ #define BTREE_UNORDERED 16 /* Use of a hash implementation is OK */ | < | 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | ** pager.h. */ #define BTREE_OMIT_JOURNAL 1 /* Do not create or use a rollback journal */ #define BTREE_NO_READLOCK 2 /* Omit readlocks on readonly files */ #define BTREE_MEMORY 4 /* This is an in-memory DB */ #define BTREE_SINGLE 8 /* The file contains at most 1 b-tree */ #define BTREE_UNORDERED 16 /* Use of a hash implementation is OK */ int sqlite3BtreeClose(Btree*); int sqlite3BtreeSetCacheSize(Btree*,int); int sqlite3BtreeSetSafetyLevel(Btree*,int,int,int); int sqlite3BtreeSyncDisabled(Btree*); int sqlite3BtreeSetPageSize(Btree *p, int nPagesize, int nReserve, int eFix); int sqlite3BtreeGetPageSize(Btree*); |
︙ | ︙ |
Changes to src/build.c.
︙ | ︙ | |||
2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 | */ static void sqlite3RefillIndex(Parse *pParse, Index *pIndex, int memRootPage){ Table *pTab = pIndex->pTable; /* The table that is indexed */ int iTab = pParse->nTab++; /* Btree cursor used for pTab */ int iIdx = pParse->nTab++; /* Btree cursor used for pIndex */ int iSorter = iTab; /* Cursor opened by OpenSorter (if in use) */ int addr1; /* Address of top of loop */ int tnum; /* Root page of index */ 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); | > < < < < < < < < < | 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 | */ static void sqlite3RefillIndex(Parse *pParse, Index *pIndex, int memRootPage){ Table *pTab = pIndex->pTable; /* The table that is indexed */ int iTab = pParse->nTab++; /* Btree cursor used for pTab */ int iIdx = pParse->nTab++; /* Btree cursor used for pIndex */ int iSorter = iTab; /* Cursor opened by OpenSorter (if in use) */ int addr1; /* Address of top of loop */ int addr2; /* Address to jump to for next iteration */ int tnum; /* Root page of index */ 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 |
︙ | ︙ | |||
2364 2365 2366 2367 2368 2369 2370 2371 | 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/expr.c.
︙ | ︙ | |||
2283 2284 2285 2286 2287 2288 2289 | AggInfo *pAggInfo = pExpr->pAggInfo; struct AggInfo_col *pCol = &pAggInfo->aCol[pExpr->iAgg]; if( !pAggInfo->directMode ){ assert( pCol->iMem>0 ); inReg = pCol->iMem; break; }else if( pAggInfo->useSortingIdx ){ | | | 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 | AggInfo *pAggInfo = pExpr->pAggInfo; struct AggInfo_col *pCol = &pAggInfo->aCol[pExpr->iAgg]; if( !pAggInfo->directMode ){ assert( pCol->iMem>0 ); inReg = pCol->iMem; break; }else if( pAggInfo->useSortingIdx ){ sqlite3VdbeAddOp3(v, OP_Column, pAggInfo->sortingIdxPTab, pCol->iSorterColumn, target); break; } /* Otherwise, fall thru into the TK_COLUMN case */ } case TK_COLUMN: { if( pExpr->iTable<0 ){ |
︙ | ︙ |
Changes to src/pager.c.
︙ | ︙ | |||
617 618 619 620 621 622 623 | u8 fullSync; /* Do extra syncs of the journal for robustness */ u8 ckptSyncFlags; /* SYNC_NORMAL or SYNC_FULL for checkpoint */ u8 syncFlags; /* SYNC_NORMAL or SYNC_FULL otherwise */ u8 tempFile; /* zFilename is a temporary file */ u8 readOnly; /* True for a read-only database */ u8 memDb; /* True to inhibit all file I/O */ u8 hasSeenStress; /* pagerStress() called one or more times */ | < | 617 618 619 620 621 622 623 624 625 626 627 628 629 630 | u8 fullSync; /* Do extra syncs of the journal for robustness */ u8 ckptSyncFlags; /* SYNC_NORMAL or SYNC_FULL for checkpoint */ u8 syncFlags; /* SYNC_NORMAL or SYNC_FULL otherwise */ u8 tempFile; /* zFilename is a temporary file */ u8 readOnly; /* True for a read-only database */ u8 memDb; /* True to inhibit all file I/O */ u8 hasSeenStress; /* pagerStress() called one or more times */ /************************************************************************** ** The following block contains those class members that change during ** routine opertion. Class members not in this block are either fixed ** when the pager is first created or else only change when there is a ** significant mode change (such as changing the page_size, locking_mode, ** or the journal_mode). From another view, these class members describe |
︙ | ︙ | |||
841 842 843 844 845 846 847 | assert( p->journalMode==PAGER_JOURNALMODE_OFF || p->journalMode==PAGER_JOURNALMODE_MEMORY ); assert( p->eState!=PAGER_ERROR && p->eState!=PAGER_OPEN ); assert( pagerUseWal(p)==0 ); } | < < < < < < < < < | 840 841 842 843 844 845 846 847 848 849 850 851 852 853 | assert( p->journalMode==PAGER_JOURNALMODE_OFF || p->journalMode==PAGER_JOURNALMODE_MEMORY ); assert( p->eState!=PAGER_ERROR && p->eState!=PAGER_OPEN ); assert( pagerUseWal(p)==0 ); } /* If changeCountDone is set, a RESERVED lock or greater must be held ** on the file. */ assert( pPager->changeCountDone==0 || pPager->eLock>=RESERVED_LOCK ); assert( p->eLock!=PENDING_LOCK ); switch( p->eState ){ |
︙ | ︙ | |||
4553 4554 4555 4556 4557 4558 4559 | }else if( memDb ){ pPager->journalMode = PAGER_JOURNALMODE_MEMORY; } /* pPager->xBusyHandler = 0; */ /* pPager->pBusyHandlerArg = 0; */ pPager->xReiniter = xReinit; /* memset(pPager->aHash, 0, sizeof(pPager->aHash)); */ | < < < < < < | 4543 4544 4545 4546 4547 4548 4549 4550 4551 4552 4553 4554 4555 4556 | }else if( memDb ){ pPager->journalMode = PAGER_JOURNALMODE_MEMORY; } /* pPager->xBusyHandler = 0; */ /* pPager->pBusyHandlerArg = 0; */ pPager->xReiniter = xReinit; /* memset(pPager->aHash, 0, sizeof(pPager->aHash)); */ *ppPager = pPager; return SQLITE_OK; } |
︙ | ︙ | |||
6103 6104 6105 6106 6107 6108 6109 | /* ** Return true if this is an in-memory pager. */ int sqlite3PagerIsMemdb(Pager *pPager){ return MEMDB; } | < < < < < < < < < < < | 6087 6088 6089 6090 6091 6092 6093 6094 6095 6096 6097 6098 6099 6100 | /* ** Return true if this is an in-memory pager. */ int sqlite3PagerIsMemdb(Pager *pPager){ return MEMDB; } /* ** Check that there are at least nSavepoint savepoints open. If there are ** currently less than nSavepoints open, then open one or more savepoints ** to make up the difference. If the number of savepoints is already ** equal to nSavepoint, then this function is a no-op. ** ** If a memory allocation fails, SQLITE_NOMEM is returned. If an error |
︙ | ︙ |
Changes to src/pager.h.
︙ | ︙ | |||
152 153 154 155 156 157 158 | const char *sqlite3PagerFilename(Pager*); const sqlite3_vfs *sqlite3PagerVfs(Pager*); sqlite3_file *sqlite3PagerFile(Pager*); const char *sqlite3PagerJournalname(Pager*); int sqlite3PagerNosync(Pager*); void *sqlite3PagerTempSpace(Pager*); int sqlite3PagerIsMemdb(Pager*); | < < < | 152 153 154 155 156 157 158 159 160 161 162 163 164 165 | const char *sqlite3PagerFilename(Pager*); const sqlite3_vfs *sqlite3PagerVfs(Pager*); sqlite3_file *sqlite3PagerFile(Pager*); const char *sqlite3PagerJournalname(Pager*); int sqlite3PagerNosync(Pager*); void *sqlite3PagerTempSpace(Pager*); int sqlite3PagerIsMemdb(Pager*); /* Functions used to truncate the database file. */ void sqlite3PagerTruncateImage(Pager*,Pgno); #if defined(SQLITE_HAS_CODEC) && !defined(SQLITE_OMIT_WAL) void *sqlite3PagerCodec(DbPage *); #endif |
︙ | ︙ |
Changes to src/select.c.
︙ | ︙ | |||
415 416 417 418 419 420 421 422 423 424 425 426 | Select *pSelect, /* The whole SELECT statement */ int regData /* Register holding data to be sorted */ ){ Vdbe *v = pParse->pVdbe; int nExpr = pOrderBy->nExpr; int regBase = sqlite3GetTempRange(pParse, nExpr+2); int regRecord = sqlite3GetTempReg(pParse); sqlite3ExprCacheClear(pParse); sqlite3ExprCodeExprList(pParse, pOrderBy, regBase, 0); sqlite3VdbeAddOp2(v, OP_Sequence, pOrderBy->iECursor, regBase+nExpr); sqlite3ExprCodeMove(pParse, regData, regBase+nExpr+1, 1); sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase, nExpr + 2, regRecord); | > > > > > > | | 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 | Select *pSelect, /* The whole SELECT statement */ int regData /* Register holding data to be sorted */ ){ Vdbe *v = pParse->pVdbe; int nExpr = pOrderBy->nExpr; int regBase = sqlite3GetTempRange(pParse, nExpr+2); int regRecord = sqlite3GetTempReg(pParse); int op; sqlite3ExprCacheClear(pParse); sqlite3ExprCodeExprList(pParse, pOrderBy, regBase, 0); sqlite3VdbeAddOp2(v, OP_Sequence, pOrderBy->iECursor, regBase+nExpr); sqlite3ExprCodeMove(pParse, regData, regBase+nExpr+1, 1); sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase, nExpr + 2, regRecord); if( pSelect->selFlags & SF_UseSorter ){ op = OP_SorterInsert; }else{ op = OP_IdxInsert; } sqlite3VdbeAddOp2(v, op, pOrderBy->iECursor, regRecord); sqlite3ReleaseTempReg(pParse, regRecord); sqlite3ReleaseTempRange(pParse, regBase, nExpr+2); if( pSelect->iLimit ){ int addr1, addr2; int iLimit; if( pSelect->iOffset ){ iLimit = pSelect->iOffset+1; |
︙ | ︙ | |||
889 890 891 892 893 894 895 | if( eDest==SRT_Output || eDest==SRT_Coroutine ){ pseudoTab = pParse->nTab++; sqlite3VdbeAddOp3(v, OP_OpenPseudo, pseudoTab, regRow, nColumn); regRowid = 0; }else{ regRowid = sqlite3GetTempReg(pParse); } | > > > > > > > > > > | | | > | 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 | if( eDest==SRT_Output || eDest==SRT_Coroutine ){ pseudoTab = pParse->nTab++; sqlite3VdbeAddOp3(v, OP_OpenPseudo, pseudoTab, regRow, nColumn); regRowid = 0; }else{ regRowid = sqlite3GetTempReg(pParse); } if( p->selFlags & SF_UseSorter ){ int regSortOut = sqlite3GetTempReg(pParse); int ptab2 = pParse->nTab++; sqlite3VdbeAddOp3(v, OP_OpenPseudo, ptab2, regSortOut, pOrderBy->nExpr+2); addr = 1 + sqlite3VdbeAddOp2(v, OP_SorterSort, iTab, addrBreak); codeOffset(v, p, addrContinue); sqlite3VdbeAddOp2(v, OP_SorterData, iTab, regSortOut); sqlite3VdbeAddOp3(v, OP_Column, ptab2, pOrderBy->nExpr+1, regRow); sqlite3VdbeChangeP5(v, OPFLAG_CLEARCACHE); }else{ addr = 1 + sqlite3VdbeAddOp2(v, OP_Sort, iTab, addrBreak); codeOffset(v, p, addrContinue); sqlite3VdbeAddOp3(v, OP_Column, iTab, pOrderBy->nExpr+1, regRow); } switch( eDest ){ case SRT_Table: case SRT_EphemTab: { testcase( eDest==SRT_Table ); testcase( eDest==SRT_EphemTab ); sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, regRowid); sqlite3VdbeAddOp3(v, OP_Insert, iParm, regRow, regRowid); |
︙ | ︙ | |||
944 945 946 947 948 949 950 | } sqlite3ReleaseTempReg(pParse, regRow); sqlite3ReleaseTempReg(pParse, regRowid); /* The bottom of the loop */ sqlite3VdbeResolveLabel(v, addrContinue); | > > > | > | 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 | } sqlite3ReleaseTempReg(pParse, regRow); sqlite3ReleaseTempReg(pParse, regRowid); /* The bottom of the loop */ sqlite3VdbeResolveLabel(v, addrContinue); if( p->selFlags & SF_UseSorter ){ sqlite3VdbeAddOp2(v, OP_SorterNext, iTab, addr); }else{ sqlite3VdbeAddOp2(v, OP_Next, iTab, addr); } sqlite3VdbeResolveLabel(v, addrBreak); if( eDest==SRT_Output || eDest==SRT_Coroutine ){ sqlite3VdbeAddOp2(v, OP_Close, pseudoTab, 0); } } /* |
︙ | ︙ | |||
3910 3911 3912 3913 3914 3915 3916 3917 3918 3919 3920 3921 3922 3923 | } /* Set the limiter. */ iEnd = sqlite3VdbeMakeLabel(v); p->nSelectRow = (double)LARGEST_INT64; computeLimitRegisters(pParse, p, iEnd); /* Open a virtual index to use for the distinct set. */ if( p->selFlags & SF_Distinct ){ KeyInfo *pKeyInfo; distinct = pParse->nTab++; pKeyInfo = keyInfoFromExprList(pParse, p->pEList); | > > > > | 3931 3932 3933 3934 3935 3936 3937 3938 3939 3940 3941 3942 3943 3944 3945 3946 3947 3948 | } /* Set the limiter. */ iEnd = sqlite3VdbeMakeLabel(v); p->nSelectRow = (double)LARGEST_INT64; computeLimitRegisters(pParse, p, iEnd); if( p->iLimit==0 && addrSortIndex>=0 ){ sqlite3VdbeGetOp(v, addrSortIndex)->opcode = OP_SorterOpen; p->selFlags |= SF_UseSorter; } /* Open a virtual index to use for the distinct set. */ if( p->selFlags & SF_Distinct ){ KeyInfo *pKeyInfo; distinct = pParse->nTab++; pKeyInfo = keyInfoFromExprList(pParse, p->pEList); |
︙ | ︙ | |||
4004 4005 4006 4007 4008 4009 4010 4011 4012 4013 4014 4015 4016 4017 | int iBMem; /* First Mem address for previous GROUP BY */ int iUseFlag; /* Mem address holding flag indicating that at least ** one row of the input to the aggregator has been ** processed */ int iAbortFlag; /* Mem address which causes query abort if positive */ int groupBySort; /* Rows come from source in GROUP BY order */ int addrEnd; /* End of processing for this SELECT */ /* Remove any and all aliases between the result set and the ** GROUP BY clause. */ if( pGroupBy ){ int k; /* Loop counter */ struct ExprList_item *pItem; /* For looping over expression in a list */ | > > | 4029 4030 4031 4032 4033 4034 4035 4036 4037 4038 4039 4040 4041 4042 4043 4044 | int iBMem; /* First Mem address for previous GROUP BY */ int iUseFlag; /* Mem address holding flag indicating that at least ** one row of the input to the aggregator has been ** processed */ int iAbortFlag; /* Mem address which causes query abort if positive */ int groupBySort; /* Rows come from source in GROUP BY order */ int addrEnd; /* End of processing for this SELECT */ int sortPTab = 0; /* Pseudotable used to decode sorting results */ int sortOut = 0; /* Output register from the sorter */ /* Remove any and all aliases between the result set and the ** GROUP BY clause. */ if( pGroupBy ){ int k; /* Loop counter */ struct ExprList_item *pItem; /* For looping over expression in a list */ |
︙ | ︙ | |||
4065 4066 4067 4068 4069 4070 4071 | int addrTopOfLoop; /* Top of the input loop */ int addrSortingIdx; /* The OP_OpenEphemeral for the sorting index */ int addrReset; /* Subroutine for resetting the accumulator */ int regReset; /* Return address register for reset subroutine */ /* If there is a GROUP BY clause we might need a sorting index to ** implement it. Allocate that sorting index now. If it turns out | | | | 4092 4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 4111 | int addrTopOfLoop; /* Top of the input loop */ int addrSortingIdx; /* The OP_OpenEphemeral for the sorting index */ int addrReset; /* Subroutine for resetting the accumulator */ int regReset; /* Return address register for reset subroutine */ /* If there is a GROUP BY clause we might need a sorting index to ** implement it. Allocate that sorting index now. If it turns out ** that we do not need it after all, the OP_SorterOpen instruction ** will be converted into a Noop. */ sAggInfo.sortingIdx = pParse->nTab++; pKeyInfo = keyInfoFromExprList(pParse, pGroupBy); addrSortingIdx = sqlite3VdbeAddOp4(v, OP_SorterOpen, sAggInfo.sortingIdx, sAggInfo.nSortingColumn, 0, (char*)pKeyInfo, P4_KEYINFO_HANDOFF); /* Initialize memory locations used by GROUP BY aggregate processing */ iUseFlag = ++pParse->nMem; iAbortFlag = ++pParse->nMem; |
︙ | ︙ | |||
4151 4152 4153 4154 4155 4156 4157 | sqlite3VdbeAddOp2(v, OP_SCopy, r2, r1); } j++; } } regRecord = sqlite3GetTempReg(pParse); sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase, nCol, regRecord); | | > > > | > > > | > | 4178 4179 4180 4181 4182 4183 4184 4185 4186 4187 4188 4189 4190 4191 4192 4193 4194 4195 4196 4197 4198 4199 4200 4201 4202 4203 4204 4205 4206 4207 4208 4209 4210 4211 4212 4213 4214 4215 4216 4217 4218 | sqlite3VdbeAddOp2(v, OP_SCopy, r2, r1); } j++; } } regRecord = sqlite3GetTempReg(pParse); sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase, nCol, regRecord); sqlite3VdbeAddOp2(v, OP_SorterInsert, sAggInfo.sortingIdx, regRecord); sqlite3ReleaseTempReg(pParse, regRecord); sqlite3ReleaseTempRange(pParse, regBase, nCol); sqlite3WhereEnd(pWInfo); sAggInfo.sortingIdxPTab = sortPTab = pParse->nTab++; sortOut = sqlite3GetTempReg(pParse); sqlite3VdbeAddOp3(v, OP_OpenPseudo, sortPTab, sortOut, nCol); sqlite3VdbeAddOp2(v, OP_SorterSort, sAggInfo.sortingIdx, addrEnd); VdbeComment((v, "GROUP BY sort")); sAggInfo.useSortingIdx = 1; sqlite3ExprCacheClear(pParse); } /* Evaluate the current GROUP BY terms and store in b0, b1, b2... ** (b0 is memory location iBMem+0, b1 is iBMem+1, and so forth) ** Then compare the current GROUP BY terms against the GROUP BY terms ** from the previous row currently stored in a0, a1, a2... */ addrTopOfLoop = sqlite3VdbeCurrentAddr(v); sqlite3ExprCacheClear(pParse); if( groupBySort ){ sqlite3VdbeAddOp2(v, OP_SorterData, sAggInfo.sortingIdx, sortOut); } for(j=0; j<pGroupBy->nExpr; j++){ if( groupBySort ){ sqlite3VdbeAddOp3(v, OP_Column, sortPTab, j, iBMem+j); if( j==0 ) sqlite3VdbeChangeP5(v, OPFLAG_CLEARCACHE); }else{ sAggInfo.directMode = 1; sqlite3ExprCode(pParse, pGroupBy->a[j].pExpr, iBMem+j); } } sqlite3VdbeAddOp4(v, OP_Compare, iAMem, iBMem, pGroupBy->nExpr, (char*)pKeyInfo, P4_KEYINFO); |
︙ | ︙ | |||
4209 4210 4211 4212 4213 4214 4215 | updateAccumulator(pParse, &sAggInfo); sqlite3VdbeAddOp2(v, OP_Integer, 1, iUseFlag); VdbeComment((v, "indicate data in accumulator")); /* End of the loop */ if( groupBySort ){ | | | 4243 4244 4245 4246 4247 4248 4249 4250 4251 4252 4253 4254 4255 4256 4257 | updateAccumulator(pParse, &sAggInfo); sqlite3VdbeAddOp2(v, OP_Integer, 1, iUseFlag); VdbeComment((v, "indicate data in accumulator")); /* End of the loop */ if( groupBySort ){ sqlite3VdbeAddOp2(v, OP_SorterNext, sAggInfo.sortingIdx, addrTopOfLoop); }else{ sqlite3WhereEnd(pWInfo); sqlite3VdbeChangeToNoop(v, addrSortingIdx, 1); } /* Output the final row of result */ |
︙ | ︙ |
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 |
︙ | ︙ | |||
1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 | */ struct AggInfo { u8 directMode; /* Direct rendering mode means take data directly ** from source tables rather than from accumulators */ u8 useSortingIdx; /* In direct mode, reference the sorting index rather ** than the source table */ int sortingIdx; /* Cursor number of the sorting index */ ExprList *pGroupBy; /* The group by clause */ int nSortingColumn; /* Number of columns in the sorting index */ struct AggInfo_col { /* For each column used in source tables */ Table *pTab; /* Source table */ int iTable; /* Cursor number of the source table */ int iColumn; /* Column number within the source table */ int iSorterColumn; /* Column number in the sorting index */ | > | 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 | */ struct AggInfo { u8 directMode; /* Direct rendering mode means take data directly ** from source tables rather than from accumulators */ u8 useSortingIdx; /* In direct mode, reference the sorting index rather ** than the source table */ int sortingIdx; /* Cursor number of the sorting index */ int sortingIdxPTab; /* Cursor number of pseudo-table */ ExprList *pGroupBy; /* The group by clause */ int nSortingColumn; /* Number of columns in the sorting index */ struct AggInfo_col { /* For each column used in source tables */ Table *pTab; /* Source table */ int iTable; /* Cursor number of the source table */ int iColumn; /* Column number within the source table */ int iSorterColumn; /* Column number in the sorting index */ |
︙ | ︙ | |||
2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 | */ #define SF_Distinct 0x0001 /* Output should be DISTINCT */ #define SF_Resolved 0x0002 /* Identifiers have been resolved */ #define SF_Aggregate 0x0004 /* Contains aggregate functions */ #define SF_UsesEphemeral 0x0008 /* Uses the OpenEphemeral opcode */ #define SF_Expanded 0x0010 /* sqlite3SelectExpand() called on this */ #define SF_HasTypeInfo 0x0020 /* FROM subqueries have Table metadata */ /* ** The results of a select can be distributed in several ways. The ** "SRT" prefix means "SELECT Result Type". */ #define SRT_Union 1 /* Store result as keys in an index */ | > | 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 | */ #define SF_Distinct 0x0001 /* Output should be DISTINCT */ #define SF_Resolved 0x0002 /* Identifiers have been resolved */ #define SF_Aggregate 0x0004 /* Contains aggregate functions */ #define SF_UsesEphemeral 0x0008 /* Uses the OpenEphemeral opcode */ #define SF_Expanded 0x0010 /* sqlite3SelectExpand() called on this */ #define SF_HasTypeInfo 0x0020 /* FROM subqueries have Table metadata */ #define SF_UseSorter 0x0040 /* Sort using a sorter */ /* ** The results of a select can be distributed in several ways. The ** "SRT" prefix means "SELECT Result Type". */ #define SRT_Union 1 /* Store result as keys in an index */ |
︙ | ︙ |
Changes to src/vdbe.c.
︙ | ︙ | |||
3158 3159 3160 3161 3162 3163 3164 | /* Opcode: OpenAutoindex P1 P2 * P4 * ** ** This opcode works the same as OP_OpenEphemeral. It has a ** different name to distinguish its use. Tables created using ** by this opcode will be used for automatically created transient ** indices in joins. */ | < < < < < < < < | 3158 3159 3160 3161 3162 3163 3164 3165 3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177 3178 3179 3180 3181 3182 | /* Opcode: OpenAutoindex P1 P2 * P4 * ** ** This opcode works the same as OP_OpenEphemeral. It has a ** different name to distinguish its use. Tables created using ** by this opcode will be used for automatically created transient ** indices in joins. */ case OP_OpenAutoindex: case OP_OpenEphemeral: { VdbeCursor *pCx; static const int vfsFlags = SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE | SQLITE_OPEN_EXCLUSIVE | SQLITE_OPEN_DELETEONCLOSE | SQLITE_OPEN_TRANSIENT_DB; assert( pOp->p1>=0 ); pCx = allocateCursor(p, pOp->p1, pOp->p2, -1, 1); if( pCx==0 ) goto no_mem; pCx->nullRow = 1; rc = sqlite3BtreeOpen(db->pVfs, 0, db, &pCx->pBt, BTREE_OMIT_JOURNAL | BTREE_SINGLE | pOp->p5, vfsFlags); if( rc==SQLITE_OK ){ rc = sqlite3BtreeBeginTrans(pCx->pBt, 1); |
︙ | ︙ | |||
3210 3211 3212 3213 3214 3215 3216 3217 | }else{ rc = sqlite3BtreeCursor(pCx->pBt, MASTER_ROOT, 1, 0, pCx->pCursor); pCx->isTable = 1; } } pCx->isOrdered = (pOp->p5!=BTREE_UNORDERED); pCx->isIndex = !pCx->isTable; #ifndef SQLITE_OMIT_MERGE_SORT | > > > > > > > > > > > > > > > | | < > > > | 3202 3203 3204 3205 3206 3207 3208 3209 3210 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 | }else{ rc = sqlite3BtreeCursor(pCx->pBt, MASTER_ROOT, 1, 0, pCx->pCursor); pCx->isTable = 1; } } pCx->isOrdered = (pOp->p5!=BTREE_UNORDERED); pCx->isIndex = !pCx->isTable; break; } /* 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 |
︙ | ︙ | |||
4065 4066 4067 4068 4069 4070 4071 4072 4073 4074 4075 4076 4077 4078 | ** This is used by trigger programs. */ case OP_ResetCount: { sqlite3VdbeSetChanges(db, p->nChange); p->nChange = 0; break; } /* Opcode: RowData P1 P2 * * * ** ** Write into register P2 the complete row data for cursor P1. ** There is no interpretation of the data. ** It is just copied onto the P2 register exactly as ** it is found in the database file. | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 4074 4075 4076 4077 4078 4079 4080 4081 4082 4083 4084 4085 4086 4087 4088 4089 4090 4091 4092 4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 4111 4112 4113 4114 4115 4116 4117 4118 4119 4120 4121 4122 4123 4124 4125 4126 | ** This is used by trigger programs. */ case OP_ResetCount: { sqlite3VdbeSetChanges(db, p->nChange); p->nChange = 0; break; } /* Opcode: SorterCompare P1 P2 P3 ** ** P1 is a sorter cursor. This instruction compares the record blob in ** register P3 with the entry that the sorter cursor currently points to. ** If, excluding the rowid fields at the end, the two records are a match, ** fall through to the next instruction. Otherwise, jump to instruction P2. */ case OP_SorterCompare: { VdbeCursor *pC; int res; pC = p->apCsr[pOp->p1]; assert( isSorter(pC) ); pIn3 = &aMem[pOp->p3]; rc = sqlite3VdbeSorterCompare(pC, pIn3, &res); if( res ){ pc = pOp->p2-1; } break; }; /* 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. ** It is just copied onto the P2 register exactly as ** it is found in the database file. |
︙ | ︙ | |||
4099 4100 4101 4102 4103 4104 4105 | pOut = &aMem[pOp->p2]; memAboutToChange(p, pOut); /* Note that RowKey and RowData are really exactly the same instruction */ assert( pOp->p1>=0 && pOp->p1<p->nCursor ); pC = p->apCsr[pOp->p1]; | > | < | < < < < < | 4147 4148 4149 4150 4151 4152 4153 4154 4155 4156 4157 4158 4159 4160 4161 4162 4163 4164 4165 4166 4167 | pOut = &aMem[pOp->p2]; memAboutToChange(p, pOut); /* Note that RowKey and RowData are really exactly the same instruction */ assert( pOp->p1>=0 && pOp->p1<p->nCursor ); 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 |
︙ | ︙ | |||
4267 4268 4269 4270 4271 4272 4273 4274 4275 4276 4277 4278 4279 4280 | ** Sorting is accomplished by writing records into a sorting index, ** 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_Sort: { /* jump */ #ifdef SQLITE_TEST sqlite3_sort_count++; sqlite3_search_count--; #endif p->aCounter[SQLITE_STMTSTATUS_SORT-1]++; /* Fall through into OP_Rewind */ | > > > > | 4310 4311 4312 4313 4314 4315 4316 4317 4318 4319 4320 4321 4322 4323 4324 4325 4326 4327 | ** Sorting is accomplished by writing records into a sorting index, ** 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 */ |
︙ | ︙ | |||
4291 4292 4293 4294 4295 4296 4297 4298 4299 4300 4301 4302 4303 4304 | VdbeCursor *pC; BtCursor *pCrsr; int res; assert( pOp->p1>=0 && pOp->p1<p->nCursor ); pC = p->apCsr[pOp->p1]; assert( pC!=0 ); res = 1; if( isSorter(pC) ){ rc = sqlite3VdbeSorterRewind(db, pC, &res); }else{ pCrsr = pC->pCursor; assert( pCrsr ); rc = sqlite3BtreeFirst(pCrsr, &res); | > | 4338 4339 4340 4341 4342 4343 4344 4345 4346 4347 4348 4349 4350 4351 4352 | VdbeCursor *pC; BtCursor *pCrsr; int res; assert( pOp->p1>=0 && pOp->p1<p->nCursor ); pC = p->apCsr[pOp->p1]; assert( pC!=0 ); assert( pC->isSorter==(pOp->opcode==OP_SorterSort) ); res = 1; if( isSorter(pC) ){ rc = sqlite3VdbeSorterRewind(db, pC, &res); }else{ pCrsr = pC->pCursor; assert( pCrsr ); rc = sqlite3BtreeFirst(pCrsr, &res); |
︙ | ︙ | |||
4343 4344 4345 4346 4347 4348 4349 4350 4351 4352 4353 4354 4355 4356 4357 4358 4359 4360 4361 4362 | ** ** 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_Prev: /* jump */ case OP_Next: { /* jump */ VdbeCursor *pC; int res; CHECK_FOR_INTERRUPT; assert( pOp->p1>=0 && pOp->p1<p->nCursor ); assert( pOp->p5<=ArraySize(p->aCounter) ); pC = p->apCsr[pOp->p1]; if( pC==0 ){ break; /* See ticket #2273 */ } if( isSorter(pC) ){ | > > > > > | | 4391 4392 4393 4394 4395 4396 4397 4398 4399 4400 4401 4402 4403 4404 4405 4406 4407 4408 4409 4410 4411 4412 4413 4414 4415 4416 4417 4418 4419 4420 4421 4422 4423 | ** ** 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 ); assert( pOp->p5<=ArraySize(p->aCounter) ); pC = p->apCsr[pOp->p1]; if( pC==0 ){ break; /* See ticket #2273 */ } assert( pC->isSorter==(pOp->opcode==OP_SorterNext) ); if( isSorter(pC) ){ assert( pOp->opcode==OP_SorterNext ); rc = sqlite3VdbeSorterNext(db, pC, &res); }else{ res = 1; assert( pC->deferredMoveto==0 ); assert( pC->pCursor ); assert( pOp->opcode!=OP_Next || pOp->p4.xAdvance==sqlite3BtreeNext ); assert( pOp->opcode!=OP_Prev || pOp->p4.xAdvance==sqlite3BtreePrevious ); |
︙ | ︙ | |||
4391 4392 4393 4394 4395 4396 4397 4398 4399 4400 4401 4402 4403 4404 4405 4406 4407 4408 4409 4410 4411 4412 4413 | ** ** 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_IdxInsert: { /* in2 */ VdbeCursor *pC; BtCursor *pCrsr; int nKey; const char *zKey; assert( pOp->p1>=0 && pOp->p1<p->nCursor ); pC = p->apCsr[pOp->p1]; assert( pC!=0 ); pIn2 = &aMem[pOp->p2]; assert( pIn2->flags & MEM_Blob ); pCrsr = pC->pCursor; if( ALWAYS(pCrsr!=0) ){ assert( pC->isTable==0 ); rc = ExpandBlob(pIn2); if( rc==SQLITE_OK ){ | > > > > > > > > | | < < | < | > | 4444 4445 4446 4447 4448 4449 4450 4451 4452 4453 4454 4455 4456 4457 4458 4459 4460 4461 4462 4463 4464 4465 4466 4467 4468 4469 4470 4471 4472 4473 4474 4475 4476 4477 4478 4479 4480 4481 4482 4483 4484 4485 4486 4487 4488 4489 | ** ** 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 ); pC = p->apCsr[pOp->p1]; assert( pC!=0 ); assert( pC->isSorter==(pOp->opcode==OP_SorterInsert) ); pIn2 = &aMem[pOp->p2]; assert( pIn2->flags & MEM_Blob ); pCrsr = pC->pCursor; if( ALWAYS(pCrsr!=0) ){ assert( pC->isTable==0 ); rc = ExpandBlob(pIn2); if( rc==SQLITE_OK ){ if( isSorter(pC) ){ rc = sqlite3VdbeSorterWrite(db, pC, pIn2); }else{ nKey = pIn2->n; zKey = pIn2->z; rc = sqlite3BtreeInsert(pCrsr, zKey, nKey, "", 0, 0, pOp->p3, ((pOp->p5 & OPFLAG_USESEEKRESULT) ? pC->seekResult : 0) ); assert( pC->deferredMoveto==0 ); pC->cacheStatus = CACHE_STALE; } } } break; } /* Opcode: IdxDelete P1 P2 P3 * * ** |
︙ | ︙ |
Changes to src/vdbeInt.h.
︙ | ︙ | |||
55 56 57 58 59 60 61 62 63 64 65 66 | Bool atFirst; /* True if pointing to first entry */ Bool useRandomRowid; /* Generate new record numbers semi-randomly */ Bool nullRow; /* True if pointing to a row with no data */ Bool deferredMoveto; /* A call to sqlite3BtreeMoveto() is needed */ Bool isTable; /* True if a table requiring integer keys */ Bool isIndex; /* True if an index containing keys only - no data */ Bool isOrdered; /* True if the underlying table is BTREE_UNORDERED */ 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 */ | > | | 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | Bool atFirst; /* True if pointing to first entry */ Bool useRandomRowid; /* Generate new record numbers semi-randomly */ Bool nullRow; /* True if pointing to a row with no data */ Bool deferredMoveto; /* A call to sqlite3BtreeMoveto() is needed */ Bool isTable; /* True if a table requiring integer keys */ Bool isIndex; /* True if an index containing keys only - no data */ 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 |
︙ | ︙ | |||
398 399 400 401 402 403 404 405 406 | #ifdef SQLITE_OMIT_MERGE_SORT # define sqlite3VdbeSorterInit(Y,Z) SQLITE_OK # define sqlite3VdbeSorterWrite(X,Y,Z) SQLITE_OK # define sqlite3VdbeSorterClose(Y,Z) # define sqlite3VdbeSorterRowkey(Y,Z) SQLITE_OK # define sqlite3VdbeSorterRewind(X,Y,Z) SQLITE_OK # define sqlite3VdbeSorterNext(X,Y,Z) SQLITE_OK #else int sqlite3VdbeSorterInit(sqlite3 *, VdbeCursor *); | > < > | > | 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 | #ifdef SQLITE_OMIT_MERGE_SORT # define sqlite3VdbeSorterInit(Y,Z) SQLITE_OK # define sqlite3VdbeSorterWrite(X,Y,Z) SQLITE_OK # define sqlite3VdbeSorterClose(Y,Z) # define sqlite3VdbeSorterRowkey(Y,Z) SQLITE_OK # define sqlite3VdbeSorterRewind(X,Y,Z) SQLITE_OK # define sqlite3VdbeSorterNext(X,Y,Z) SQLITE_OK # define sqlite3VdbeSorterCompare(X,Y,Z) SQLITE_OK #else int sqlite3VdbeSorterInit(sqlite3 *, VdbeCursor *); void sqlite3VdbeSorterClose(sqlite3 *, VdbeCursor *); int sqlite3VdbeSorterRowkey(VdbeCursor *, Mem *); int sqlite3VdbeSorterNext(sqlite3 *, VdbeCursor *, int *); int sqlite3VdbeSorterRewind(sqlite3 *, VdbeCursor *, int *); int sqlite3VdbeSorterWrite(sqlite3 *, VdbeCursor *, Mem *); int sqlite3VdbeSorterCompare(VdbeCursor *, Mem *, int *); #endif #if !defined(SQLITE_OMIT_SHARED_CACHE) && SQLITE_THREADSAFE>0 void sqlite3VdbeEnter(Vdbe*); void sqlite3VdbeLeave(Vdbe*); #else # define sqlite3VdbeEnter(X) |
︙ | ︙ |
Changes to src/vdbeaux.c.
︙ | ︙ | |||
429 430 431 432 433 434 435 | }else if( opcode==OP_VFilter ){ int n; assert( p->nOp - i >= 3 ); assert( pOp[-1].opcode==OP_Integer ); n = pOp[-1].p1; if( n>nMaxArgs ) nMaxArgs = n; #endif | | | 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 | }else if( opcode==OP_VFilter ){ int n; assert( p->nOp - i >= 3 ); assert( pOp[-1].opcode==OP_Integer ); n = pOp[-1].p1; if( n>nMaxArgs ) nMaxArgs = n; #endif }else if( opcode==OP_Next || opcode==OP_SorterNext ){ pOp->p4.xAdvance = sqlite3BtreeNext; pOp->p4type = P4_ADVANCE; }else if( opcode==OP_Prev ){ pOp->p4.xAdvance = sqlite3BtreePrevious; pOp->p4type = P4_ADVANCE; } |
︙ | ︙ |
Changes to src/vdbesort.c.
︙ | ︙ | |||
17 18 19 20 21 22 23 24 25 26 27 28 29 30 | #include "sqliteInt.h" #include "vdbeInt.h" #ifndef SQLITE_OMIT_MERGE_SORT typedef struct VdbeSorterIter VdbeSorterIter; /* ** NOTES ON DATA STRUCTURE USED FOR N-WAY MERGES: ** ** As keys are added to the sorter, they are written to disk in a series ** of sorted packed-memory-arrays (PMAs). The size of each PMA is roughly ** the same as the cache-size allowed for temporary databases. In order | > | 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #include "sqliteInt.h" #include "vdbeInt.h" #ifndef SQLITE_OMIT_MERGE_SORT typedef struct VdbeSorterIter VdbeSorterIter; typedef struct SorterRecord SorterRecord; /* ** NOTES ON DATA STRUCTURE USED FOR N-WAY MERGES: ** ** As keys are added to the sorter, they are written to disk in a series ** of sorted packed-memory-arrays (PMAs). The size of each PMA is roughly ** the same as the cache-size allowed for temporary databases. In order |
︙ | ︙ | |||
88 89 90 91 92 93 94 | ** aTree[] = { X, 0 0, 6 0, 3, 5, 6 } ** ** In other words, each time we advance to the next sorter element, log2(N) ** key comparison operations are required, where N is the number of segments ** being merged (rounded up to the next power of 2). */ struct VdbeSorter { | | < > > > > > > > > > > > > > > > > | 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 | ** aTree[] = { X, 0 0, 6 0, 3, 5, 6 } ** ** In other words, each time we advance to the next sorter element, log2(N) ** key comparison operations are required, where N is the number of segments ** being merged (rounded up to the next power of 2). */ struct VdbeSorter { int nInMemory; /* Current size of pRecord list as PMA */ int nTree; /* Used size of aTree/aIter (power of 2) */ VdbeSorterIter *aIter; /* Array of iterators to merge */ int *aTree; /* Current state of incremental merge */ i64 iWriteOff; /* Current write offset within file pTemp1 */ i64 iReadOff; /* Current read offset within file pTemp1 */ sqlite3_file *pTemp1; /* PMA file 1 */ int nPMA; /* Number of PMAs stored in pTemp1 */ SorterRecord *pRecord; /* Head of in-memory record list */ int mnPmaSize; /* Minimum PMA size, in bytes */ int mxPmaSize; /* Maximum PMA size, in bytes. 0==no limit */ char *aSpace; /* Space for UnpackRecord() */ int nSpace; /* Size of aSpace in bytes */ }; /* ** 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 */ sqlite3_file *pFile; /* File iterator is reading from */ int nAlloc; /* Bytes of space at aAlloc */ u8 *aAlloc; /* Allocated space */ int nKey; /* Number of bytes in key */ u8 *aKey; /* Pointer to current key */ }; /* ** A structure to store a single record. All in-memory records are connected ** together into a linked list headed at VdbeSorter.pRecord using the ** SorterRecord.pNext pointer. */ struct SorterRecord { void *pVal; int nVal; SorterRecord *pNext; }; /* Minimum allowable value for the VdbeSorter.nWorking variable */ #define SORTER_MIN_WORKING 10 /* Maximum number of segments to merge in a single pass. */ #define SORTER_MAX_MERGE_COUNT 16 |
︙ | ︙ | |||
271 272 273 274 275 276 277 278 279 280 281 282 283 284 | } if( rc==SQLITE_OK ){ rc = vdbeSorterIterNext(db, pIter); } return rc; } /* ** This function is called to compare two iterator keys when merging ** multiple b-tree segments. Parameter iOut is the index of the aTree[] ** value to recalculate. */ static int vdbeSorterDoCompare(VdbeCursor *pCsr, int iOut){ VdbeSorter *pSorter = pCsr->pSorter; | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 | } if( rc==SQLITE_OK ){ rc = vdbeSorterIterNext(db, pIter); } return rc; } /* ** Compare key1 (buffer pKey1, size nKey1 bytes) with key2 (buffer pKey2, ** size nKey2 bytes). Argument pKeyInfo supplies the collation functions ** used by the comparison. If an error occurs, return an SQLite error code. ** Otherwise, return SQLITE_OK and set *pRes to a negative, zero or positive ** value, depending on whether key1 is smaller, equal to or larger than key2. ** ** If the bOmitRowid argument is non-zero, assume both keys end in a rowid ** field. For the purposes of the comparison, ignore it. Also, if bOmitRowid ** is true and key1 contains even a single NULL value, it is considered to ** be less than key2. Even if key2 also contains NULL values. ** ** If pKey2 is passed a NULL pointer, then it is assumed that the pCsr->aSpace ** has been allocated and contains an unpacked record that is used as key2. */ static int vdbeSorterCompare( VdbeCursor *pCsr, /* Cursor object (for pKeyInfo) */ int bOmitRowid, /* Ignore rowid field at end of keys */ void *pKey1, int nKey1, /* Left side of comparison */ void *pKey2, int nKey2, /* Right side of comparison */ int *pRes /* OUT: Result of comparison */ ){ KeyInfo *pKeyInfo = pCsr->pKeyInfo; VdbeSorter *pSorter = pCsr->pSorter; char *aSpace = pSorter->aSpace; int nSpace = pSorter->nSpace; UnpackedRecord *r2; int i; if( aSpace==0 ){ nSpace = ROUND8(sizeof(UnpackedRecord))+(pKeyInfo->nField+1)*sizeof(Mem); aSpace = (char *)sqlite3Malloc(nSpace); if( aSpace==0 ) return SQLITE_NOMEM; pSorter->aSpace = aSpace; pSorter->nSpace = nSpace; } if( pKey2 ){ /* This call cannot fail. As the memory is already allocated. */ r2 = sqlite3VdbeRecordUnpack(pKeyInfo, nKey2, pKey2, aSpace, nSpace); assert( r2 && (r2->flags & UNPACKED_NEED_FREE)==0 ); assert( r2==aSpace ); }else{ r2 = (UnpackedRecord *)aSpace; assert( !bOmitRowid ); } if( bOmitRowid ){ for(i=0; i<r2->nField-1; i++){ if( r2->aMem[i].flags & MEM_Null ){ *pRes = -1; return SQLITE_OK; } } r2->flags |= UNPACKED_PREFIX_MATCH; r2->nField--; assert( r2->nField>0 ); } *pRes = sqlite3VdbeRecordCompare(nKey1, pKey1, r2); return SQLITE_OK; } /* ** This function is called to compare two iterator keys when merging ** multiple b-tree segments. Parameter iOut is the index of the aTree[] ** value to recalculate. */ static int vdbeSorterDoCompare(VdbeCursor *pCsr, int iOut){ VdbeSorter *pSorter = pCsr->pSorter; |
︙ | ︙ | |||
302 303 304 305 306 307 308 | p2 = &pSorter->aIter[i2]; if( p1->pFile==0 ){ iRes = i2; }else if( p2->pFile==0 ){ iRes = i1; }else{ | < < | | | | | < < > > > > | | > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | | | < < | < < | > | > > > | | | | < | | < < < | < < | < < < < < < < < < < < < < < | | | | | < | | | | | < | < < < < < < < < < < | | > > > | < | | | < | | > > | | < < < | < | < | | < < < < < < < < | > > > | < > > | | | < | | | < < < | < < | < | | < < < | 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 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 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 | p2 = &pSorter->aIter[i2]; if( p1->pFile==0 ){ iRes = i2; }else if( p2->pFile==0 ){ iRes = i1; }else{ int res; int rc = vdbeSorterCompare( pCsr, 0, p1->aKey, p1->nKey, p2->aKey, p2->nKey, &res ); if( rc!=SQLITE_OK ) return rc; if( res<=0 ){ iRes = i1; }else{ iRes = i2; } } pSorter->aTree[iOut] = iRes; return SQLITE_OK; } /* ** Initialize the temporary index cursor just opened as a sorter cursor. */ int sqlite3VdbeSorterInit(sqlite3 *db, VdbeCursor *pCsr){ int pgsz; /* Page size of main database */ int mxCache; /* Cache size */ VdbeSorter *pSorter; /* The new sorter */ 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. */ static void vdbeSorterRecordFree(sqlite3 *db, SorterRecord *pRecord){ SorterRecord *p; SorterRecord *pNext; for(p=pRecord; p; p=pNext){ pNext = p->pNext; sqlite3DbFree(db, p); } } /* ** Free any cursor components allocated by sqlite3VdbeSorterXXX routines. */ void sqlite3VdbeSorterClose(sqlite3 *db, VdbeCursor *pCsr){ VdbeSorter *pSorter = pCsr->pSorter; if( pSorter ){ if( pSorter->aIter ){ int i; for(i=0; i<pSorter->nTree; i++){ vdbeSorterIterZero(db, &pSorter->aIter[i]); } sqlite3DbFree(db, pSorter->aIter); } if( pSorter->pTemp1 ){ sqlite3OsCloseFree(pSorter->pTemp1); } vdbeSorterRecordFree(db, pSorter->pRecord); sqlite3_free(pSorter->aSpace); sqlite3DbFree(db, pSorter); pCsr->pSorter = 0; } } /* ** Allocate space for a file-handle and open a temporary file. If successful, ** set *ppFile to point to the malloc'd file-handle and return SQLITE_OK. ** Otherwise, set *ppFile to 0 and return an SQLite error code. */ static int vdbeSorterOpenTempFile(sqlite3 *db, sqlite3_file **ppFile){ int dummy; return sqlite3OsOpenMalloc(db->pVfs, 0, ppFile, SQLITE_OPEN_TEMP_JOURNAL | SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE | SQLITE_OPEN_EXCLUSIVE | SQLITE_OPEN_DELETEONCLOSE, &dummy ); } /* ** Attemp to merge the two sorted lists p1 and p2 into a single list. If no ** error occurs set *ppOut to the head of the new list and return SQLITE_OK. */ static int vdbeSorterMerge( sqlite3 *db, /* Database handle */ VdbeCursor *pCsr, /* For pKeyInfo */ SorterRecord *p1, /* First list to merge */ SorterRecord *p2, /* Second list to merge */ SorterRecord **ppOut /* OUT: Head of merged list */ ){ int rc = SQLITE_OK; SorterRecord *pFinal = 0; SorterRecord **pp = &pFinal; void *pVal2 = p2 ? p2->pVal : 0; while( p1 && p2 ){ int res; rc = vdbeSorterCompare(pCsr, 0, p1->pVal, p1->nVal, pVal2, p2->nVal, &res); if( rc!=SQLITE_OK ){ *pp = 0; vdbeSorterRecordFree(db, p1); vdbeSorterRecordFree(db, p2); vdbeSorterRecordFree(db, pFinal); *ppOut = 0; return rc; } if( res<=0 ){ *pp = p1; pp = &p1->pNext; p1 = p1->pNext; pVal2 = 0; }else{ *pp = p2; pp = &p2->pNext; p2 = p2->pNext; if( p2==0 ) break; pVal2 = p2->pVal; } } *pp = p1 ? p1 : p2; *ppOut = pFinal; return SQLITE_OK; } /* ** 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(sqlite3 *db, VdbeCursor *pCsr){ int rc = SQLITE_OK; int i; SorterRecord **aSlot; SorterRecord *p; VdbeSorter *pSorter = pCsr->pSorter; aSlot = (SorterRecord **)sqlite3MallocZero(64 * sizeof(SorterRecord *)); if( !aSlot ){ return SQLITE_NOMEM; } p = pSorter->pRecord; while( p ){ SorterRecord *pNext = p->pNext; p->pNext = 0; for(i=0; rc==SQLITE_OK && aSlot[i]; i++){ rc = vdbeSorterMerge(db, pCsr, p, aSlot[i], &p); aSlot[i] = 0; } if( rc!=SQLITE_OK ){ vdbeSorterRecordFree(db, pNext); break; } aSlot[i] = p; p = pNext; } p = 0; for(i=0; i<64; i++){ if( rc==SQLITE_OK ){ rc = vdbeSorterMerge(db, pCsr, p, aSlot[i], &p); }else{ vdbeSorterRecordFree(db, aSlot[i]); } } pSorter->pRecord = p; sqlite3_free(aSlot); return rc; } /* ** Write the current contents of the in-memory linked-list to a PMA. Return ** SQLITE_OK if successful, or an SQLite error code otherwise. ** ** The format of a PMA is: ** ** * 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(sqlite3 *db, VdbeCursor *pCsr){ int rc = SQLITE_OK; /* Return code */ VdbeSorter *pSorter = pCsr->pSorter; if( pSorter->nInMemory==0 ){ assert( pSorter->pRecord==0 ); return rc; } rc = vdbeSorterSort(db, pCsr); /* If the first temporary PMA file has not been opened, open it now. */ if( rc==SQLITE_OK && pSorter->pTemp1==0 ){ rc = vdbeSorterOpenTempFile(db, &pSorter->pTemp1); assert( rc!=SQLITE_OK || pSorter->pTemp1 ); assert( pSorter->iWriteOff==0 ); assert( pSorter->nPMA==0 ); } if( rc==SQLITE_OK ){ i64 iOff = pSorter->iWriteOff; SorterRecord *p; SorterRecord *pNext = 0; pSorter->nPMA++; rc = vdbeSorterWriteVarint(pSorter->pTemp1, pSorter->nInMemory, &iOff); for(p=pSorter->pRecord; rc==SQLITE_OK && p; p=pNext){ pNext = p->pNext; rc = vdbeSorterWriteVarint(pSorter->pTemp1, p->nVal, &iOff); if( rc==SQLITE_OK ){ rc = sqlite3OsWrite(pSorter->pTemp1, p->pVal, p->nVal, iOff); iOff += p->nVal; } sqlite3DbFree(db, p); } /* This assert verifies that unless an error has occurred, the size of ** the PMA on disk is the same as the expected size stored in ** pSorter->nInMemory. */ assert( rc!=SQLITE_OK || pSorter->nInMemory==( iOff-pSorter->iWriteOff-sqlite3VarintLen(pSorter->nInMemory) )); pSorter->iWriteOff = iOff; pSorter->pRecord = p; } return rc; } /* ** Add a record to the sorter. */ int sqlite3VdbeSorterWrite( sqlite3 *db, /* Database handle */ VdbeCursor *pCsr, /* Sorter cursor */ Mem *pVal /* Memory cell containing record */ ){ VdbeSorter *pSorter = pCsr->pSorter; int rc = SQLITE_OK; /* Return Code */ SorterRecord *pNew; /* New list element */ assert( pSorter ); pSorter->nInMemory += sqlite3VarintLen(pVal->n) + pVal->n; pNew = (SorterRecord *)sqlite3DbMallocRaw(db, pVal->n + sizeof(SorterRecord)); if( pNew==0 ){ rc = SQLITE_NOMEM; }else{ pNew->pVal = (void *)&pNew[1]; memcpy(pNew->pVal, pVal->z, pVal->n); pNew->nVal = pVal->n; pNew->pNext = pSorter->pRecord; pSorter->pRecord = pNew; } /* See if the contents of the sorter should now be written out. They ** are written out when either of the following are true: ** ** * 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; } return rc; } /* ** Helper function for sqlite3VdbeSorterRewind(). */ static int vdbeSorterInitMerge( |
︙ | ︙ | |||
572 573 574 575 576 577 578 | 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 ); | | | | < | > | > > > > | 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 | 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)); |
︙ | ︙ | |||
667 668 669 670 671 672 673 | } /* ** Advance to the next element in the sorter. */ int sqlite3VdbeSorterNext(sqlite3 *db, VdbeCursor *pCsr, int *pbEof){ VdbeSorter *pSorter = pCsr->pSorter; | > > > | | < | | | | | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | < | < < < < < | < | | > > > > > > > > > > > > > > > > > > > > > > > > > | 822 823 824 825 826 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 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 | } /* ** 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 ** the comparison, ignore the rowid field at the end of each record. ** ** If an error occurs, return an SQLite error code (i.e. SQLITE_NOMEM). ** Otherwise, set *pRes to a negative, zero or positive value if the ** key in pVal is smaller than, equal to or larger than the current sorter ** key. */ 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, 1, pVal->z, pVal->n, pKey, nKey, pRes); assert( rc!=SQLITE_OK || pVal->db->mallocFailed || (*pRes)<=0 ); return rc; } #endif /* #ifndef SQLITE_OMIT_MERGE_SORT */ |
Changes to test/distinct.test.
︙ | ︙ | |||
41 42 43 44 45 46 47 | uplevel [list do_test $tn [list is_distinct_noop $sql] 0] } proc do_temptables_test {tn sql temptables} { uplevel [list do_test $tn [subst -novar { set ret "" db eval "EXPLAIN [set sql]" { | | | 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | uplevel [list do_test $tn [list is_distinct_noop $sql] 0] } proc do_temptables_test {tn sql temptables} { uplevel [list do_test $tn [subst -novar { set ret "" db eval "EXPLAIN [set sql]" { if {$opcode == "OpenEphemeral" || $opcode == "SorterOpen"} { if {$p5 != "10" && $p5!="00"} { error "p5 = $p5" } if {$p5 == "10"} { lappend ret hash } else { lappend ret btree } } |
︙ | ︙ |
Changes to test/index4.test.
︙ | ︙ | |||
104 105 106 107 108 109 110 111 112 | DROP TABLE t1; CREATE TABLE t1(x); COMMIT; CREATE INDEX i1 ON t1(x); PRAGMA integrity_check } {ok} finish_test | > > > > > > > > > > > > > > | 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 | DROP TABLE t1; CREATE TABLE t1(x); COMMIT; CREATE INDEX i1 ON t1(x); PRAGMA integrity_check } {ok} do_execsql_test 2.1 { BEGIN; CREATE TABLE t2(x); INSERT INTO t2 VALUES(14); INSERT INTO t2 VALUES(35); INSERT INTO t2 VALUES(15); INSERT INTO t2 VALUES(35); INSERT INTO t2 VALUES(16); COMMIT; } do_catchsql_test 2.2 { CREATE UNIQUE INDEX i3 ON t2(x); } {1 {indexed columns are not unique}} finish_test |