Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Get ORDER BY working for recursive queries. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | cte-via-queue |
Files: | files | file ages | folders |
SHA1: |
37b343b01841b338954ddfa9b76d92aa |
User & Date: | drh 2014-01-22 17:28:35.279 |
Context
2014-01-22
| ||
18:07 | Add support for LIMIT and OFFSET in a recursive query. (Closed-Leaf check-in: 1945484e6b user: drh tags: cte-via-queue) | |
17:28 | Get ORDER BY working for recursive queries. (check-in: 37b343b018 user: drh tags: cte-via-queue) | |
13:35 | Add new SelectDest codes, SRT_Queue and SRT_DistQueue in anticipation of adding ORDER BY support on recursive queries. Factor out the recursive query code generator into a separate procedure. (check-in: 3eb5f9f8d6 user: drh tags: cte-via-queue) | |
Changes
Changes to src/select.c.
︙ | ︙ | |||
577 578 579 580 581 582 583 | /* Pull the requested columns. */ nResultCol = pEList->nExpr; if( pDest->iSdst==0 ){ pDest->iSdst = pParse->nMem+1; pDest->nSdst = nResultCol; pParse->nMem += nResultCol; | < < | 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 | /* 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)); } |
︙ | ︙ | |||
660 661 662 663 664 665 666 | } switch( eDest ){ /* In this mode, write each query result to the key of the temporary ** table iParm. */ #ifndef SQLITE_OMIT_COMPOUND_SELECT | < < < < < < < < < < < < < < < < < < < < | 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 | } 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 |
︙ | ︙ | |||
804 805 806 807 808 809 810 811 812 813 814 815 816 817 | 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 ** user-defined functions that have side effects. We do not care ** about the actual results of the select. */ | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 | sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm); }else{ sqlite3VdbeAddOp2(v, OP_ResultRow, regResult, nResultCol); sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol); } break; } #ifndef SQLITE_OMIT_CTE /* Write the results into a priority queue that is order according to ** pDest->pOrderBy (in pSO). pDest->iSDParm (in iParm) is the cursor for an ** index with pSO->nExpr+2 columns. Build a key using pSO for the first ** pSO->nExpr columns, then make sure all keys are unique by adding a ** final OP_Sequence column. The last column is the record as a blob. */ case SRT_DistQueue: case SRT_Queue: { int nKey; int r1, r2, r3; int addrTest = 0; ExprList *pSO; pSO = pDest->pOrderBy; assert( pSO ); nKey = pSO->nExpr; r1 = sqlite3GetTempReg(pParse); r2 = sqlite3GetTempRange(pParse, nKey+2); r3 = r2+nKey+1; sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r3); if( eDest==SRT_DistQueue ){ /* If the destination is DistQueue, then cursor (iParm+1) is open ** on a second ephemeral index that holds all values every previously ** added to the queue. Only add this new value if it has never before ** been added */ addrTest = sqlite3VdbeAddOp4Int(v, OP_Found, iParm+1, 0, r3, 0); sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm+1, r3); } for(i=0; i<nKey; i++){ sqlite3VdbeAddOp2(v, OP_SCopy, regResult + pSO->a[i].u.x.iOrderByCol - 1, r2+i); } sqlite3VdbeAddOp2(v, OP_Sequence, iParm, r2+nKey); sqlite3VdbeAddOp3(v, OP_MakeRecord, r2, nKey+2, r1); sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1); if( addrTest ) sqlite3VdbeJumpHere(v, addrTest); sqlite3ReleaseTempReg(pParse, r1); sqlite3ReleaseTempRange(pParse, r2, nKey+2); break; } #endif /* SQLITE_OMIT_CTE */ #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 ** user-defined functions that have side effects. We do not care ** about the actual results of the select. */ |
︙ | ︙ | |||
893 894 895 896 897 898 899 | ** then the KeyInfo structure is appropriate for initializing a virtual ** index to implement a DISTINCT test. ** ** Space to hold the KeyInfo structure is obtain from malloc. The calling ** function is responsible for seeing that this structure is eventually ** freed. */ | | | | 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 | ** then the KeyInfo structure is appropriate for initializing a virtual ** index to implement a DISTINCT test. ** ** Space to hold the KeyInfo structure is obtain from malloc. The calling ** function is responsible for seeing that this structure is eventually ** freed. */ static KeyInfo *keyInfoFromExprList(Parse *pParse, ExprList *pList, int nExtra){ int nExpr; KeyInfo *pInfo; struct ExprList_item *pItem; sqlite3 *db = pParse->db; int i; nExpr = pList->nExpr; pInfo = sqlite3KeyInfoAlloc(db, nExpr+nExtra, 1); if( pInfo ){ assert( sqlite3KeyInfoIsWriteable(pInfo) ); for(i=0, pItem=pList->a; i<nExpr; i++, pItem++){ CollSeq *pColl; pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr); if( !pColl ) pColl = db->pDfltColl; pInfo->aColl[i] = pColl; |
︙ | ︙ | |||
1709 1710 1711 1712 1713 1714 1715 | ** ** ** There is exactly one reference to the recursive-table in the FROM clause ** of recursive-query, marked with the SrcList->a[].isRecursive flag. ** ** The setup-query runs once to generate an initial set of rows that go ** into a Queue table. Rows are extracted from the Queue table one by | | | | | 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 | ** ** ** There is exactly one reference to the recursive-table in the FROM clause ** of recursive-query, marked with the SrcList->a[].isRecursive flag. ** ** The setup-query runs once to generate an initial set of rows that go ** into a Queue table. Rows are extracted from the Queue table one by ** one. Each row extracted from Queue is output to pDest. Then the single ** extracted row (now in the iCurrent table) becomes the content of the ** recursive-table for a recursive-query run. The output of the recursive-query ** is added back into the Queue table. Then another row is extracted from Queue ** and the iteration continues until the Queue table is empty. ** ** If the compound query operator is UNION then no duplicate rows are ever ** inserted into the Queue table. The iDistinct table keeps a copy of all rows ** that have ever been inserted into Queue and causes duplicates to be ** discarded. If the operator is UNION ALL, then duplicates are allowed. |
︙ | ︙ | |||
1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 | int regCurrent; /* Register holding Current table */ int iQueue; /* The Queue table */ int iDistinct = 0; /* To ensure unique results if UNION */ int eDest = SRT_Table; /* How to write to Queue */ SelectDest destQueue; /* SelectDest targetting the Queue table */ int i; /* Loop counter */ int rc; /* Result code */ /* Obtain authorization to do a recursive query */ if( sqlite3AuthCheck(pParse, SQLITE_RECURSIVE, 0, 0, 0) ) return; addrBreak = sqlite3VdbeMakeLabel(v); | > < < | > > > > | | < | < > > > > > > > > | > > | < < < > > > | > > > > > > > > > > > | 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 | int regCurrent; /* Register holding Current table */ int iQueue; /* The Queue table */ int iDistinct = 0; /* To ensure unique results if UNION */ int eDest = SRT_Table; /* How to write to Queue */ SelectDest destQueue; /* SelectDest targetting the Queue table */ int i; /* Loop counter */ int rc; /* Result code */ ExprList *pOrderBy; /* The ORDER BY clause */ /* Obtain authorization to do a recursive query */ if( sqlite3AuthCheck(pParse, SQLITE_RECURSIVE, 0, 0, 0) ) return; addrBreak = sqlite3VdbeMakeLabel(v); /* Check that there is no ORDER BY or LIMIT clause. Neither of these ** are currently supported on recursive queries. */ assert( p->pOffset==0 || p->pLimit ); if( /*p->pOrderBy ||*/ p->pLimit ){ sqlite3ErrorMsg(pParse, "%s in a recursive query", p->pOrderBy ? "ORDER BY" : "LIMIT" ); return; } /* Locate the cursor number of the Current table */ for(i=0; ALWAYS(i<pSrc->nSrc); i++){ if( pSrc->a[i].isRecursive ){ iCurrent = pSrc->a[i].iCursor; break; } } /* Detach the ORDER BY clause from the compound SELECT */ pOrderBy = p->pOrderBy; p->pOrderBy = 0; /* Allocate cursors numbers for Queue and Distinct. The cursor number for ** the Distinct table must be exactly one greater than Queue in order ** for the SRT_DistTable and SRT_DistQueue destinations to work. */ iQueue = pParse->nTab++; if( p->op==TK_UNION ){ eDest = pOrderBy ? SRT_DistQueue : SRT_DistTable; iDistinct = pParse->nTab++; }else{ eDest = pOrderBy ? SRT_Queue : SRT_Table; } sqlite3SelectDestInit(&destQueue, eDest, iQueue); /* Allocate cursors for Current, Queue, and Distinct. */ regCurrent = ++pParse->nMem; sqlite3VdbeAddOp3(v, OP_OpenPseudo, iCurrent, regCurrent, nCol); if( pOrderBy ){ KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pOrderBy, 1); sqlite3VdbeAddOp4(v, OP_OpenEphemeral, iQueue, pOrderBy->nExpr+2, 0, (char*)pKeyInfo, P4_KEYINFO); destQueue.pOrderBy = pOrderBy; }else{ sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iQueue, nCol); } VdbeComment((v, "Queue table")); if( iDistinct ){ p->addrOpenEphm[0] = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iDistinct, 0); p->selFlags |= SF_UsesEphemeral; } /* Store the results of the setup-query in Queue. */ rc = sqlite3Select(pParse, pSetup, &destQueue); if( rc ) goto end_of_recursive_query; /* Find the next row in the Queue and output that row */ addrTop = sqlite3VdbeAddOp2(v, OP_Rewind, iQueue, addrBreak); /* Transfer the next row in Queue over to Current */ sqlite3VdbeAddOp1(v, OP_NullRow, iCurrent); /* To reset column cache */ if( pOrderBy ){ sqlite3VdbeAddOp3(v, OP_Column, iQueue, pOrderBy->nExpr+1, regCurrent); }else{ sqlite3VdbeAddOp2(v, OP_RowData, iQueue, regCurrent); } sqlite3VdbeAddOp1(v, OP_Delete, iQueue); /* Output the single row in Current */ addrCont = sqlite3VdbeMakeLabel(v); selectInnerLoop(pParse, p, p->pEList, iCurrent, 0, 0, pDest, addrCont, addrBreak); sqlite3VdbeResolveLabel(v, addrCont); /* Execute the recursive SELECT taking the single row in Current as ** the value for the recursive-table. Store the results in the Queue. */ p->pPrior = 0; sqlite3Select(pParse, p, &destQueue); assert( p->pPrior==0 ); p->pPrior = pSetup; /* Keep running the loop until the Queue is empty */ sqlite3VdbeAddOp2(v, OP_Goto, 0, addrTop); sqlite3VdbeResolveLabel(v, addrBreak); end_of_recursive_query: p->pOrderBy = pOrderBy; return; } #endif /* Forward references */ static int multiSelectOrderBy( Parse *pParse, /* Parsing context */ Select *p, /* The right-most of SELECTs to be coded */ |
︙ | ︙ | |||
4223 4224 4225 4226 4227 4228 4229 | Expr *pE = pFunc->pExpr; assert( !ExprHasProperty(pE, EP_xIsSelect) ); if( pE->x.pList==0 || pE->x.pList->nExpr!=1 ){ sqlite3ErrorMsg(pParse, "DISTINCT aggregates must have exactly one " "argument"); pFunc->iDistinct = -1; }else{ | | | 4268 4269 4270 4271 4272 4273 4274 4275 4276 4277 4278 4279 4280 4281 4282 | Expr *pE = pFunc->pExpr; assert( !ExprHasProperty(pE, EP_xIsSelect) ); if( pE->x.pList==0 || pE->x.pList->nExpr!=1 ){ sqlite3ErrorMsg(pParse, "DISTINCT aggregates must have exactly one " "argument"); pFunc->iDistinct = -1; }else{ KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pE->x.pList, 0); sqlite3VdbeAddOp4(v, OP_OpenEphemeral, pFunc->iDistinct, 0, 0, (char*)pKeyInfo, P4_KEYINFO); } } } } |
︙ | ︙ | |||
4632 4633 4634 4635 4636 4637 4638 | ** extracted in pre-sorted order. If that is the case, then the ** OP_OpenEphemeral instruction will be changed to an OP_Noop once ** we figure out that the sorting index is not needed. The addrSortIndex ** variable is used to facilitate that change. */ if( pOrderBy ){ KeyInfo *pKeyInfo; | | | 4677 4678 4679 4680 4681 4682 4683 4684 4685 4686 4687 4688 4689 4690 4691 | ** extracted in pre-sorted order. If that is the case, then the ** OP_OpenEphemeral instruction will be changed to an OP_Noop once ** we figure out that the sorting index is not needed. The addrSortIndex ** variable is used to facilitate that change. */ if( pOrderBy ){ KeyInfo *pKeyInfo; pKeyInfo = keyInfoFromExprList(pParse, pOrderBy, 0); pOrderBy->iECursor = pParse->nTab++; p->addrOpenEphm[2] = addrSortIndex = sqlite3VdbeAddOp4(v, OP_OpenEphemeral, pOrderBy->iECursor, pOrderBy->nExpr+2, 0, (char*)pKeyInfo, P4_KEYINFO); }else{ addrSortIndex = -1; |
︙ | ︙ | |||
4664 4665 4666 4667 4668 4669 4670 | /* Open a virtual index to use for the distinct set. */ if( p->selFlags & SF_Distinct ){ sDistinct.tabTnct = pParse->nTab++; sDistinct.addrTnct = sqlite3VdbeAddOp4(v, OP_OpenEphemeral, sDistinct.tabTnct, 0, 0, | | | 4709 4710 4711 4712 4713 4714 4715 4716 4717 4718 4719 4720 4721 4722 4723 | /* Open a virtual index to use for the distinct set. */ if( p->selFlags & SF_Distinct ){ sDistinct.tabTnct = pParse->nTab++; sDistinct.addrTnct = sqlite3VdbeAddOp4(v, OP_OpenEphemeral, sDistinct.tabTnct, 0, 0, (char*)keyInfoFromExprList(pParse, p->pEList, 0), P4_KEYINFO); sqlite3VdbeChangeP5(v, BTREE_UNORDERED); sDistinct.eTnctType = WHERE_DISTINCT_UNORDERED; }else{ sDistinct.eTnctType = WHERE_DISTINCT_NOOP; } |
︙ | ︙ | |||
4788 4789 4790 4791 4792 4793 4794 | /* 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++; | | | 4833 4834 4835 4836 4837 4838 4839 4840 4841 4842 4843 4844 4845 4846 4847 | /* 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, 0); addrSortingIdx = sqlite3VdbeAddOp4(v, OP_SorterOpen, sAggInfo.sortingIdx, sAggInfo.nSortingColumn, 0, (char*)pKeyInfo, P4_KEYINFO); /* Initialize memory locations used by GROUP BY aggregate processing */ iUseFlag = ++pParse->nMem; |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
2247 2248 2249 2250 2251 2252 2253 | #define SRT_DistQueue 13 /* Like SRT_Queue, but unique results only */ /* ** An instance of this object describes where to put of the results of ** a SELECT statement. */ struct SelectDest { | | | | | | > | 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 | #define SRT_DistQueue 13 /* Like SRT_Queue, but unique results only */ /* ** An instance of this object describes where to put of the results of ** a SELECT statement. */ struct SelectDest { u8 eDest; /* How to dispose of the results. On of SRT_* above. */ char affSdst; /* Affinity used when eDest==SRT_Set */ int iSDParm; /* A parameter used by the eDest disposal method */ int iSdst; /* Base register where results are written */ int nSdst; /* Number of registers allocated */ ExprList *pOrderBy; /* Key columns for SRT_Queue and SRT_DistQueue */ }; /* ** During code generation of statements that do inserts into AUTOINCREMENT ** tables, the following information is attached to the Table.u.autoInc.p ** pointer of each autoincrement table to record some side information that ** the code generator needs. We have to keep per-table autoincrement |
︙ | ︙ |
Changes to test/with1.test.
︙ | ︙ | |||
148 149 150 151 152 153 154 | WITH i(x) AS ( VALUES(1) UNION ALL SELECT x+1 FROM i) SELECT x FROM i LIMIT 10; } {1 2 3 4 5 6 7 8 9 10} do_catchsql_test 5.2 { WITH i(x) AS ( VALUES(1) UNION ALL SELECT x+1 FROM i ORDER BY 1) SELECT x FROM i LIMIT 10; | > > > > > > > > > > > > > > > > > > > > > > > | > > > > > > > > > > > > > > | 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 | WITH i(x) AS ( VALUES(1) UNION ALL SELECT x+1 FROM i) SELECT x FROM i LIMIT 10; } {1 2 3 4 5 6 7 8 9 10} do_catchsql_test 5.2 { WITH i(x) AS ( VALUES(1) UNION ALL SELECT x+1 FROM i ORDER BY 1) SELECT x FROM i LIMIT 10; } {0 {1 2 3 4 5 6 7 8 9 10}} do_execsql_test 5.2.1 { CREATE TABLE edge(xfrom, xto, seq, PRIMARY KEY(xfrom, xto)) WITHOUT ROWID; INSERT INTO edge VALUES(0, 1, 10); INSERT INTO edge VALUES(1, 2, 20); INSERT INTO edge VALUES(0, 3, 30); INSERT INTO edge VALUES(2, 4, 40); INSERT INTO edge VALUES(3, 4, 40); INSERT INTO edge VALUES(2, 5, 50); INSERT INTO edge VALUES(3, 6, 60); INSERT INTO edge VALUES(5, 7, 70); INSERT INTO edge VALUES(3, 7, 70); INSERT INTO edge VALUES(4, 8, 80); INSERT INTO edge VALUES(7, 8, 80); INSERT INTO edge VALUES(8, 9, 90); WITH RECURSIVE ancest(id, mtime) AS (VALUES(0, 0) UNION SELECT edge.xto, edge.seq FROM edge, ancest WHERE edge.xfrom=ancest.id ORDER BY 2 ) SELECT * FROM ancest; } {0 0 1 10 2 20 3 30 4 40 5 50 6 60 7 70 8 80 9 90} do_execsql_test 5.2.2 { WITH RECURSIVE ancest(id, mtime) AS (VALUES(0, 0) UNION ALL SELECT edge.xto, edge.seq FROM edge, ancest WHERE edge.xfrom=ancest.id ORDER BY 2 ) SELECT * FROM ancest; } {0 0 1 10 2 20 3 30 4 40 4 40 5 50 6 60 7 70 7 70 8 80 8 80 8 80 8 80 9 90 9 90 9 90 9 90} do_catchsql_test 5.3 { WITH i(x) AS ( VALUES(1) UNION ALL SELECT x+1 FROM i LIMIT 10 ) SELECT x FROM i LIMIT 10; } {1 {LIMIT in a recursive query}} do_execsql_test 5.4 { |
︙ | ︙ |