Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Experimental code-generator changes to utilize new opcodes for sorting. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | merge-sort |
Files: | files | file ages | folders |
SHA1: |
bab2e560f6cb989c83a96aad60f66696 |
User & Date: | drh 2011-09-01 15:32:47.873 |
Context
2011-09-01
| ||
16:01 | Use OP_SorterOpen instead of OP_OpenEphemeral to implement GROUP BY. (check-in: ebf819aaa5 user: drh tags: merge-sort) | |
15:32 | Experimental code-generator changes to utilize new opcodes for sorting. (check-in: bab2e560f6 user: drh tags: merge-sort) | |
2011-08-31
| ||
23:57 | Avoid using uninitialized variables after failures in the merge sort code. (check-in: 2869ed2829 user: drh tags: trunk) | |
Changes
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); |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
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 */ | > | 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 | */ #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.
︙ | ︙ | |||
3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177 3178 3179 | ** ** 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_OpenSorter: case OP_OpenAutoindex: case OP_OpenEphemeral: { VdbeCursor *pCx; static const int vfsFlags = SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE | SQLITE_OPEN_EXCLUSIVE | SQLITE_OPEN_DELETEONCLOSE | | > | 3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177 3178 3179 3180 | ** ** 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_OpenSorter: case OP_OpenAutoindex: case OP_SorterOpen: case OP_OpenEphemeral: { VdbeCursor *pCx; static const int vfsFlags = SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE | SQLITE_OPEN_EXCLUSIVE | SQLITE_OPEN_DELETEONCLOSE | |
︙ | ︙ | |||
3210 3211 3212 3213 3214 3215 3216 3217 3218 3219 3220 3221 3222 3223 | }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 if( rc==SQLITE_OK && pOp->opcode==OP_OpenSorter ){ rc = sqlite3VdbeSorterInit(db, pCx); } #endif break; } | > | 3211 3212 3213 3214 3215 3216 3217 3218 3219 3220 3221 3222 3223 3224 3225 | }else{ rc = sqlite3BtreeCursor(pCx->pBt, MASTER_ROOT, 1, 0, pCx->pCursor); pCx->isTable = 1; } } pCx->isOrdered = (pOp->p5!=BTREE_UNORDERED); pCx->isIndex = !pCx->isTable; pCx->isSorter = pOp->opcode==OP_SorterOpen; #ifndef SQLITE_OMIT_MERGE_SORT if( rc==SQLITE_OK && pOp->opcode==OP_OpenSorter ){ rc = sqlite3VdbeSorterInit(db, pCx); } #endif break; } |
︙ | ︙ | |||
4086 4087 4088 4089 4090 4091 4092 4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 | ** There is no interpretation of the data. ** The key is copied onto the P3 register exactly as ** it is found in the database file. ** ** If the P1 cursor must be pointing to a valid row (not a NULL row) ** of a real table, not a pseudo-table. */ case OP_RowKey: case OP_RowData: { VdbeCursor *pC; BtCursor *pCrsr; u32 n; i64 n64; 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]; | > | > | 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 | ** There is no interpretation of the data. ** The key is copied onto the P3 register exactly as ** it is found in the database file. ** ** If the P1 cursor must be pointing to a valid row (not a NULL row) ** of a real table, not a pseudo-table. */ case OP_SorterData: case OP_RowKey: case OP_RowData: { VdbeCursor *pC; BtCursor *pCrsr; u32 n; i64 n64; 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->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==(pOp->opcode==OP_SorterData) ); if( isSorter(pC) ){ assert( pOp->opcode==OP_RowKey ); rc = sqlite3VdbeSorterRowkey(pC, pOut); break; } |
︙ | ︙ | |||
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 */ | > | 4271 4272 4273 4274 4275 4276 4277 4278 4279 4280 4281 4282 4283 4284 4285 | ** 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 */ 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); | > | 4296 4297 4298 4299 4300 4301 4302 4303 4304 4305 4306 4307 4308 4309 4310 | 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 4363 4364 4365 4366 4367 4368 | ** ** 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) ){ assert( pOp->opcode==OP_Next ); rc = sqlite3VdbeSorterNext(db, pC, &res); }else{ res = 1; assert( pC->deferredMoveto==0 ); assert( pC->pCursor ); | > > | 4349 4350 4351 4352 4353 4354 4355 4356 4357 4358 4359 4360 4361 4362 4363 4364 4365 4366 4367 4368 4369 4370 4371 4372 4373 4374 4375 4376 | ** ** 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 ); 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_Next ); rc = sqlite3VdbeSorterNext(db, pC, &res); }else{ res = 1; assert( pC->deferredMoveto==0 ); assert( pC->pCursor ); |
︙ | ︙ | |||
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 ){ | > > | 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 | ** ** 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: 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 ){ |
︙ | ︙ |
Changes to src/vdbeInt.h.
︙ | ︙ | |||
55 56 57 58 59 60 61 62 63 64 65 66 67 68 | 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 */ VdbeSorter *pSorter; /* Sorter object for OP_OpenSorter cursors */ | > | 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | 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_OpenSorter cursors */ |
︙ | ︙ |
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; } |
︙ | ︙ |