Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Remove an unnecessary parameter from selectInnerLoop(). Clean up comments. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | cte-via-queue |
Files: | files | file ages | folders |
SHA1: |
5e6c4a55f6df30da9dbaa8170f322361 |
User & Date: | drh 2014-01-22 00:23:49.966 |
Context
2014-01-22
| ||
10:22 | Fix a typo in a comment. No changes to code or tests. (check-in: cceacc0e79 user: dan tags: cte-via-queue) | |
00:23 | Remove an unnecessary parameter from selectInnerLoop(). Clean up comments. (check-in: 5e6c4a55f6 user: drh tags: cte-via-queue) | |
2014-01-21
| ||
22:25 | Change the recursive common table expression algorithm to use a queue instead of a pair of tables. Runs about 25% faster on the sudoku solver query. The OP_SwapCursors opcode is no longer required. The current implementation uses just a fifo, but the plan is to change it into a queue that will support ORDER BY and LIMIT in a recursive query. (check-in: b2671e1133 user: drh tags: cte-via-queue) | |
Changes
Changes to src/select.c.
︙ | ︙ | |||
539 540 541 542 543 544 545 | int addrTnct; /* Address of OP_OpenEphemeral opcode for tabTnct */ }; /* ** This routine generates the code for the inside of the inner loop ** of a SELECT. ** | | | | | < < < < < | < | | > < < < | | | | | | | | | | 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 688 689 690 691 692 693 694 695 696 697 698 699 | int addrTnct; /* Address of OP_OpenEphemeral opcode for tabTnct */ }; /* ** This routine generates the code for the inside of the inner loop ** of a SELECT. ** ** If srcTab is negative, then the pEList expressions ** are evaluated in order to get the data for this row. If srcTab is ** zero or more, then data is pulled from srcTab and pEList is used only ** to get number columns and the datatype for each column. */ static void selectInnerLoop( Parse *pParse, /* The parser context */ Select *p, /* The complete select statement being coded */ ExprList *pEList, /* List of values being extracted */ int srcTab, /* Pull data from this table */ ExprList *pOrderBy, /* If not NULL, sort results using this key */ DistinctCtx *pDistinct, /* If not NULL, info on how to process DISTINCT */ SelectDest *pDest, /* How to dispose of the results */ int iContinue, /* Jump here to continue with next row */ int iBreak /* Jump here to break out of the inner loop */ ){ Vdbe *v = pParse->pVdbe; int i; int hasDistinct; /* True if the DISTINCT keyword is present */ int regResult; /* Start of memory holding result set */ int eDest = pDest->eDest; /* How to dispose of results */ int iParm = pDest->iSDParm; /* First argument to disposal method */ int nResultCol; /* Number of result columns */ assert( v ); assert( pEList!=0 ); hasDistinct = pDistinct ? pDistinct->eTnctType : WHERE_DISTINCT_NOOP; if( pOrderBy==0 && !hasDistinct ){ codeOffset(v, p, iContinue); } /* Pull the requested columns. */ nResultCol = pEList->nExpr; if( pDest->iSdst==0 ){ pDest->iSdst = pParse->nMem+1; pDest->nSdst = nResultCol; pParse->nMem += nResultCol; }else{ assert( pDest->nSdst==nResultCol ); } regResult = pDest->iSdst; if( srcTab>=0 ){ for(i=0; i<nResultCol; i++){ sqlite3VdbeAddOp3(v, OP_Column, srcTab, i, regResult+i); VdbeComment((v, "%s", pEList->a[i].zName)); } }else if( eDest!=SRT_Exists ){ /* If the destination is an EXISTS(...) expression, the actual ** values returned by the SELECT are not required. */ sqlite3ExprCodeExprList(pParse, pEList, regResult, (eDest==SRT_Output)?SQLITE_ECEL_DUP:0); } /* If the DISTINCT keyword was present on the SELECT statement ** and this row has been seen before, then do not make this row ** part of the result. */ if( hasDistinct ){ switch( pDistinct->eTnctType ){ case WHERE_DISTINCT_ORDERED: { VdbeOp *pOp; /* No longer required OpenEphemeral instr. */ int iJump; /* Jump destination */ int regPrev; /* Previous row content */ /* Allocate space for the previous row */ regPrev = pParse->nMem+1; pParse->nMem += nResultCol; /* Change the OP_OpenEphemeral coded earlier to an OP_Null ** sets the MEM_Cleared bit on the first register of the ** previous value. This will cause the OP_Ne below to always ** fail on the first iteration of the loop even if the first ** row is all NULLs. */ sqlite3VdbeChangeToNoop(v, pDistinct->addrTnct); pOp = sqlite3VdbeGetOp(v, pDistinct->addrTnct); pOp->opcode = OP_Null; pOp->p1 = 1; pOp->p2 = regPrev; iJump = sqlite3VdbeCurrentAddr(v) + nResultCol; for(i=0; i<nResultCol; i++){ CollSeq *pColl = sqlite3ExprCollSeq(pParse, pEList->a[i].pExpr); if( i<nResultCol-1 ){ sqlite3VdbeAddOp3(v, OP_Ne, regResult+i, iJump, regPrev+i); }else{ sqlite3VdbeAddOp3(v, OP_Eq, regResult+i, iContinue, regPrev+i); } sqlite3VdbeChangeP4(v, -1, (const char *)pColl, P4_COLLSEQ); sqlite3VdbeChangeP5(v, SQLITE_NULLEQ); } assert( sqlite3VdbeCurrentAddr(v)==iJump ); sqlite3VdbeAddOp3(v, OP_Copy, regResult, regPrev, nResultCol-1); break; } case WHERE_DISTINCT_UNIQUE: { sqlite3VdbeChangeToNoop(v, pDistinct->addrTnct); break; } default: { assert( pDistinct->eTnctType==WHERE_DISTINCT_UNORDERED ); codeDistinct(pParse, pDistinct->tabTnct, iContinue, nResultCol, regResult); break; } } if( pOrderBy==0 ){ codeOffset(v, p, iContinue); } } switch( eDest ){ /* In this mode, write each query result to the key of the temporary ** table iParm. */ #ifndef SQLITE_OMIT_COMPOUND_SELECT case SRT_Union: { int r1; r1 = sqlite3GetTempReg(pParse); sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r1); sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1); sqlite3ReleaseTempReg(pParse, r1); break; } /* Construct a record from the query result, but instead of ** saving that record, use it as a key to delete elements from ** the temporary table iParm. */ case SRT_Except: { sqlite3VdbeAddOp3(v, OP_IdxDelete, iParm, regResult, nResultCol); break; } #endif /* Store the result as data using a unique key. */ case SRT_DistTable: case SRT_Table: case SRT_EphemTab: { int r1 = sqlite3GetTempReg(pParse); testcase( eDest==SRT_Table ); testcase( eDest==SRT_EphemTab ); sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r1); #ifndef SQLITE_OMIT_CTE if( eDest==SRT_DistTable ){ /* If the destination is DistTable, then cursor (iParm+1) is open ** on an ephemeral index. If the current row is already present ** in the index, do not write it to the output. If not, add the ** current row to the index and proceed with writing it to the ** output table as well. */ |
︙ | ︙ | |||
726 727 728 729 730 731 732 | #ifndef SQLITE_OMIT_SUBQUERY /* If we are creating a set for an "expr IN (SELECT ...)" construct, ** then there should be a single item on the stack. Write this ** item into the set table with bogus data. */ case SRT_Set: { | | | 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 | #ifndef SQLITE_OMIT_SUBQUERY /* If we are creating a set for an "expr IN (SELECT ...)" construct, ** then there should be a single item on the stack. Write this ** item into the set table with bogus data. */ case SRT_Set: { assert( nResultCol==1 ); pDest->affSdst = sqlite3CompareAffinity(pEList->a[0].pExpr, pDest->affSdst); if( pOrderBy ){ /* At first glance you would think we could optimize out the ** ORDER BY in this case since the order of entries in the set ** does not matter. But there might be a LIMIT clause, in which ** case the order does matter */ |
︙ | ︙ | |||
758 759 760 761 762 763 764 | } /* If this is a scalar select that is part of an expression, then ** store the results in the appropriate memory cell and break out ** of the scan loop. */ case SRT_Mem: { | | | | | | 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 | } /* If this is a scalar select that is part of an expression, then ** store the results in the appropriate memory cell and break out ** of the scan loop. */ case SRT_Mem: { assert( nResultCol==1 ); if( pOrderBy ){ pushOntoSorter(pParse, pOrderBy, p, regResult); }else{ sqlite3ExprCodeMove(pParse, regResult, iParm, 1); /* The LIMIT clause will jump out of the loop for us */ } break; } #endif /* #ifndef SQLITE_OMIT_SUBQUERY */ /* Send the data to the callback function or to a subroutine. In the ** case of a subroutine, the subroutine itself is responsible for ** popping the data from the stack. */ case SRT_Coroutine: case SRT_Output: { testcase( eDest==SRT_Coroutine ); testcase( eDest==SRT_Output ); if( pOrderBy ){ int r1 = sqlite3GetTempReg(pParse); sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r1); pushOntoSorter(pParse, pOrderBy, p, r1); sqlite3ReleaseTempReg(pParse, r1); }else if( eDest==SRT_Coroutine ){ sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm); }else{ sqlite3VdbeAddOp2(v, OP_ResultRow, regResult, nResultCol); sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol); } break; } #if !defined(SQLITE_OMIT_TRIGGER) /* Discard the results. This is used for SELECT statements inside ** the body of a TRIGGER. The purpose of such selects is to call |
︙ | ︙ | |||
1853 1854 1855 1856 1857 1858 1859 | /* Store the results of the initial SELECT in Queue. */ rc = sqlite3Select(pParse, pPrior, &destQueue); if( rc ) goto multi_select_end; /* Find the next row in the Queue and output that row */ addrTop = sqlite3VdbeAddOp2(v, OP_Rewind, iQueue, addrBreak); | | | 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 | /* Store the results of the initial SELECT in Queue. */ rc = sqlite3Select(pParse, pPrior, &destQueue); if( rc ) goto multi_select_end; /* Find the next row in the Queue and output that row */ addrTop = sqlite3VdbeAddOp2(v, OP_Rewind, iQueue, addrBreak); selectInnerLoop(pParse, p, p->pEList, iQueue, 0, 0, &dest, addrCont, addrBreak); sqlite3VdbeResolveLabel(v, addrCont); /* Transfer the next row in Queue over to Current */ sqlite3VdbeAddOp1(v, OP_NullRow, iCurrent); /* To reset column cache */ sqlite3VdbeAddOp2(v, OP_RowData, iQueue, regCurrent); sqlite3VdbeAddOp1(v, OP_Delete, iQueue); |
︙ | ︙ | |||
2016 2017 2018 2019 2020 2021 2022 | generateColumnNames(pParse, 0, pFirst->pEList); } iBreak = sqlite3VdbeMakeLabel(v); iCont = sqlite3VdbeMakeLabel(v); computeLimitRegisters(pParse, p, iBreak); sqlite3VdbeAddOp2(v, OP_Rewind, unionTab, iBreak); iStart = sqlite3VdbeCurrentAddr(v); | | | 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 | generateColumnNames(pParse, 0, pFirst->pEList); } iBreak = sqlite3VdbeMakeLabel(v); iCont = sqlite3VdbeMakeLabel(v); computeLimitRegisters(pParse, p, iBreak); sqlite3VdbeAddOp2(v, OP_Rewind, unionTab, iBreak); iStart = sqlite3VdbeCurrentAddr(v); selectInnerLoop(pParse, p, p->pEList, unionTab, 0, 0, &dest, iCont, iBreak); sqlite3VdbeResolveLabel(v, iCont); sqlite3VdbeAddOp2(v, OP_Next, unionTab, iStart); sqlite3VdbeResolveLabel(v, iBreak); sqlite3VdbeAddOp2(v, OP_Close, unionTab, 0); } break; |
︙ | ︙ | |||
2094 2095 2096 2097 2098 2099 2100 | iCont = sqlite3VdbeMakeLabel(v); computeLimitRegisters(pParse, p, iBreak); sqlite3VdbeAddOp2(v, OP_Rewind, tab1, iBreak); r1 = sqlite3GetTempReg(pParse); iStart = sqlite3VdbeAddOp2(v, OP_RowKey, tab1, r1); sqlite3VdbeAddOp4Int(v, OP_NotFound, tab2, iCont, r1, 0); sqlite3ReleaseTempReg(pParse, r1); | | | 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 | iCont = sqlite3VdbeMakeLabel(v); computeLimitRegisters(pParse, p, iBreak); sqlite3VdbeAddOp2(v, OP_Rewind, tab1, iBreak); r1 = sqlite3GetTempReg(pParse); iStart = sqlite3VdbeAddOp2(v, OP_RowKey, tab1, r1); sqlite3VdbeAddOp4Int(v, OP_NotFound, tab2, iCont, r1, 0); sqlite3ReleaseTempReg(pParse, r1); selectInnerLoop(pParse, p, p->pEList, tab1, 0, 0, &dest, iCont, iBreak); sqlite3VdbeResolveLabel(v, iCont); sqlite3VdbeAddOp2(v, OP_Next, tab1, iStart); sqlite3VdbeResolveLabel(v, iBreak); sqlite3VdbeAddOp2(v, OP_Close, tab2, 0); sqlite3VdbeAddOp2(v, OP_Close, tab1, 0); break; |
︙ | ︙ | |||
4295 4296 4297 4298 4299 4300 4301 | #else # define explainSimpleCount(a,b,c) #endif /* ** Generate code for the SELECT statement given in the p argument. ** | < | < < < < < < < < < < < < < < < < < < < < < < | < < < < < < < < < < < < < < < < < < < | 4287 4288 4289 4290 4291 4292 4293 4294 4295 4296 4297 4298 4299 4300 4301 4302 | #else # define explainSimpleCount(a,b,c) #endif /* ** Generate code for the SELECT statement given in the p argument. ** ** The results are returned according to the SelectDest structure. ** See comments in sqliteInt.h for further information. ** ** This routine returns the number of errors. If any errors are ** encountered, then an appropriate error message is left in ** pParse->zErrMsg. ** ** This routine does NOT free the Select structure passed in. The ** calling function needs to do that. |
︙ | ︙ | |||
4679 4680 4681 4682 4683 4684 4685 | */ if( addrSortIndex>=0 && pOrderBy==0 ){ sqlite3VdbeChangeToNoop(v, addrSortIndex); p->addrOpenEphm[2] = -1; } /* Use the standard inner loop. */ | | | 4629 4630 4631 4632 4633 4634 4635 4636 4637 4638 4639 4640 4641 4642 4643 | */ if( addrSortIndex>=0 && pOrderBy==0 ){ sqlite3VdbeChangeToNoop(v, addrSortIndex); p->addrOpenEphm[2] = -1; } /* Use the standard inner loop. */ selectInnerLoop(pParse, p, pEList, -1, pOrderBy, &sDistinct, pDest, sqlite3WhereContinueLabel(pWInfo), sqlite3WhereBreakLabel(pWInfo)); /* End the database scan loop. */ sqlite3WhereEnd(pWInfo); }else{ |
︙ | ︙ | |||
4951 4952 4953 4954 4955 4956 4957 | sqlite3VdbeResolveLabel(v, addrOutputRow); addrOutputRow = sqlite3VdbeCurrentAddr(v); sqlite3VdbeAddOp2(v, OP_IfPos, iUseFlag, addrOutputRow+2); VdbeComment((v, "Groupby result generator entry point")); sqlite3VdbeAddOp1(v, OP_Return, regOutputRow); finalizeAggFunctions(pParse, &sAggInfo); sqlite3ExprIfFalse(pParse, pHaving, addrOutputRow+1, SQLITE_JUMPIFNULL); | | | 4901 4902 4903 4904 4905 4906 4907 4908 4909 4910 4911 4912 4913 4914 4915 | sqlite3VdbeResolveLabel(v, addrOutputRow); addrOutputRow = sqlite3VdbeCurrentAddr(v); sqlite3VdbeAddOp2(v, OP_IfPos, iUseFlag, addrOutputRow+2); VdbeComment((v, "Groupby result generator entry point")); sqlite3VdbeAddOp1(v, OP_Return, regOutputRow); finalizeAggFunctions(pParse, &sAggInfo); sqlite3ExprIfFalse(pParse, pHaving, addrOutputRow+1, SQLITE_JUMPIFNULL); selectInnerLoop(pParse, p, p->pEList, -1, pOrderBy, &sDistinct, pDest, addrOutputRow+1, addrSetAbort); sqlite3VdbeAddOp1(v, OP_Return, regOutputRow); VdbeComment((v, "end groupby result generator")); /* Generate a subroutine that will reset the group-by accumulator */ |
︙ | ︙ | |||
5094 5095 5096 5097 5098 5099 5100 | } sqlite3WhereEnd(pWInfo); finalizeAggFunctions(pParse, &sAggInfo); } pOrderBy = 0; sqlite3ExprIfFalse(pParse, pHaving, addrEnd, SQLITE_JUMPIFNULL); | | | 5044 5045 5046 5047 5048 5049 5050 5051 5052 5053 5054 5055 5056 5057 5058 | } sqlite3WhereEnd(pWInfo); finalizeAggFunctions(pParse, &sAggInfo); } pOrderBy = 0; sqlite3ExprIfFalse(pParse, pHaving, addrEnd, SQLITE_JUMPIFNULL); selectInnerLoop(pParse, p, p->pEList, -1, 0, 0, pDest, addrEnd, addrEnd); sqlite3ExprListDelete(db, pDel); } sqlite3VdbeResolveLabel(v, addrEnd); } /* endif aggregate query */ |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
2163 2164 2165 2166 2167 2168 2169 | #define SF_Materialize 0x0100 /* Force materialization of views */ #define SF_NestedFrom 0x0200 /* Part of a parenthesized FROM clause */ #define SF_MaybeConvert 0x0400 /* Need convertCompoundSelectToSubquery() */ #define SF_Recursive 0x0800 /* The recursive part of a recursive CTE */ /* | | | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 | #define SF_Materialize 0x0100 /* Force materialization of views */ #define SF_NestedFrom 0x0200 /* Part of a parenthesized FROM clause */ #define SF_MaybeConvert 0x0400 /* Need convertCompoundSelectToSubquery() */ #define SF_Recursive 0x0800 /* The recursive part of a recursive CTE */ /* ** The results of a SELECT can be distributed in several ways, as defined ** by one of the following macros. The "SRT" prefix means "SELECT Result ** Type". ** ** SRT_Union Store results as a key in a temporary index ** identified by pDest->iSDParm. ** ** SRT_Except Remove results from the temporary index pDest->iSDParm. ** ** SRT_Exists Store a 1 in memory cell pDest->iSDParm if the result ** set is not empty. ** ** SRT_Discard Throw the results away. This is used by SELECT ** statements within triggers whose only purpose is ** the side-effects of functions. ** ** All of the above are free to ignore their ORDER BY clause. Those that ** follow must honor the ORDER BY clause. ** ** SRT_Output Generate a row of output (using the OP_ResultRow ** opcode) for each row in the result set. ** ** SRT_Mem Only valid if the result is a single column. ** Store the first column of the first result row ** in register pDest->iSDParm then abandon the rest ** of the query. This destination implies "LIMIT 1". ** ** SRT_Set The result must be a single column. Store each ** row of result as the key in table pDest->iSDParm. ** Apply the affinity pDest->affSdst before storing ** results. Used to implement "IN (SELECT ...)". ** ** SRT_Table Store results in temporary table pDest->iSDParm. ** This is like SRT_EphemTab except that the table ** is assumed to already be open. ** ** SRT_EphemTab Create an temporary table pDest->iSDParm and store ** the result there. The cursor is left open after ** returning. This is like SRT_Table except that ** this destination uses OP_OpenEphemeral to create ** the table first. ** ** SRT_Coroutine Generate a co-routine that returns a new row of ** results each time it is invoked. The entry point ** of the co-routine is stored in register pDest->iSDParm ** and the result row is stored in pDest->nDest registers ** starting with pDest->iSdst. ** ** SRT_DistTable Store results in a temporary table pDest->iSDParm. ** But also use temporary table pDest->iSDParm+1 as ** a record of all prior results and ignore any duplicate ** rows. Name means: "Distinct Table". */ #define SRT_Union 1 /* Store result as keys in an index */ #define SRT_Except 2 /* Remove result from a UNION index */ #define SRT_Exists 3 /* Store 1 if the result is not empty */ #define SRT_Discard 4 /* Do not save the results anywhere */ /* The ORDER BY clause is ignored for all of the above */ |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 | /* Case 6: There is no usable index. We must do a complete ** scan of the entire table. */ static const u8 aStep[] = { OP_Next, OP_Prev }; static const u8 aStart[] = { OP_Rewind, OP_Last }; assert( bRev==0 || bRev==1 ); if( pTabItem->isRecursive ){ pLevel->op = OP_Noop; }else{ pLevel->op = aStep[bRev]; pLevel->p1 = iCur; pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk); pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP; } | > > | 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 3422 | /* Case 6: There is no usable index. We must do a complete ** scan of the entire table. */ static const u8 aStep[] = { OP_Next, OP_Prev }; static const u8 aStart[] = { OP_Rewind, OP_Last }; assert( bRev==0 || bRev==1 ); if( pTabItem->isRecursive ){ /* Tables marked isRecursive have only a single row that is stored in ** a pseudo-cursor. Need need to Rewind or Next such cursors. */ pLevel->op = OP_Noop; }else{ pLevel->op = aStep[bRev]; pLevel->p1 = iCur; pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk); pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP; } |
︙ | ︙ |