Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Allow only a single recursive reference in a recursive CTE. Also require that this reference is not part of a sub-query. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | common-table-expr |
Files: | files | file ages | folders |
SHA1: |
a296b73360d34c9364eceb2cc09a9a92 |
User & Date: | dan 2014-01-16 18:34:33.041 |
Context
2014-01-16
| ||
21:02 | Improve the error messages used to report illegal recursive cte references. (check-in: 54eee9fe99 user: dan tags: common-table-expr) | |
18:34 | Allow only a single recursive reference in a recursive CTE. Also require that this reference is not part of a sub-query. (check-in: a296b73360 user: dan tags: common-table-expr) | |
10:58 | Disable the flattening optimization if the parent query is the recursive part of a recursive CTE and the sub-query is a compound query. (check-in: 6bfa387e82 user: dan tags: common-table-expr) | |
Changes
Changes to src/expr.c.
︙ | ︙ | |||
1061 1062 1063 1064 1065 1066 1067 | pNew->iOffset = 0; pNew->selFlags = p->selFlags & ~SF_UsesEphemeral; pNew->pRightmost = 0; pNew->addrOpenEphm[0] = -1; pNew->addrOpenEphm[1] = -1; pNew->addrOpenEphm[2] = -1; pNew->pWith = withDup(db, p->pWith); | < | 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 | pNew->iOffset = 0; pNew->selFlags = p->selFlags & ~SF_UsesEphemeral; pNew->pRightmost = 0; pNew->addrOpenEphm[0] = -1; pNew->addrOpenEphm[1] = -1; pNew->addrOpenEphm[2] = -1; pNew->pWith = withDup(db, p->pWith); return pNew; } #else Select *sqlite3SelectDup(sqlite3 *db, Select *p, int flags){ assert( p==0 ); return 0; } |
︙ | ︙ |
Changes to src/select.c.
︙ | ︙ | |||
1740 1741 1742 1743 1744 1745 1746 | int iSub2; /* EQP id of right-hand query */ #endif /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs. Only ** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT. */ assert( p && p->pPrior ); /* Calling function guarantees this much */ | | | 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 | int iSub2; /* EQP id of right-hand query */ #endif /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs. Only ** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT. */ assert( p && p->pPrior ); /* Calling function guarantees this much */ assert( (p->selFlags & SF_Recursive)==0 || p->op==TK_ALL || p->op==TK_UNION ); db = pParse->db; pPrior = p->pPrior; assert( pPrior->pRightmost!=pPrior ); assert( pPrior->pRightmost==p->pRightmost ); dest = *pDest; if( pPrior->pOrderBy ){ sqlite3ErrorMsg(pParse,"ORDER BY clause should come after %s not before", |
︙ | ︙ | |||
1790 1791 1792 1793 1794 1795 1796 | goto multi_select_end; } #ifndef SQLITE_OMIT_CTE /* If this is a recursive query, check that there is no ORDER BY or ** LIMIT clause. Neither of these are supported. */ assert( p->pOffset==0 || p->pLimit ); | | | > > | > > > | > > > > | 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 | goto multi_select_end; } #ifndef SQLITE_OMIT_CTE /* If this is a recursive query, check that there is no ORDER BY or ** LIMIT clause. Neither of these are supported. */ assert( p->pOffset==0 || p->pLimit ); if( (p->selFlags & SF_Recursive) && (p->pOrderBy || p->pLimit) ){ sqlite3ErrorMsg(pParse, "%s in a recursive query is not allowed", p->pOrderBy ? "ORDER BY" : "LIMIT" ); goto multi_select_end; } if( p->selFlags & SF_Recursive ){ SrcList *pSrc = p->pSrc; int nCol = p->pEList->nExpr; int addrNext; int addrSwap; int iCont, iBreak; int tmp1; /* Intermediate table */ int tmp2; /* Next intermediate table */ int tmp3 = 0; /* To ensure unique results if UNION */ int eDest = SRT_Table; SelectDest tmp2dest; int i; iBreak = sqlite3VdbeMakeLabel(v); iCont = sqlite3VdbeMakeLabel(v); for(i=0; ALWAYS(i<pSrc->nSrc); i++){ if( pSrc->a[i].isRecursive ){ tmp1 = pSrc->a[i].iCursor; break; } } tmp2 = pParse->nTab++; if( p->op==TK_UNION ){ eDest = SRT_DistTable; tmp3 = pParse->nTab++; } sqlite3SelectDestInit(&tmp2dest, eDest, tmp2); |
︙ | ︙ | |||
1844 1845 1846 1847 1848 1849 1850 | sqlite3VdbeResolveLabel(v, iCont); sqlite3VdbeAddOp2(v, OP_Next, tmp1, addrNext); /* Execute the recursive SELECT. Store the results in tmp2. While this ** SELECT is running, the contents of tmp1 are read by recursive ** references to the current CTE. */ p->pPrior = 0; | < < < < | 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 | sqlite3VdbeResolveLabel(v, iCont); sqlite3VdbeAddOp2(v, OP_Next, tmp1, addrNext); /* Execute the recursive SELECT. Store the results in tmp2. While this ** SELECT is running, the contents of tmp1 are read by recursive ** references to the current CTE. */ p->pPrior = 0; rc = sqlite3Select(pParse, p, &tmp2dest); assert( p->pPrior==0 ); p->pPrior = pPrior; if( rc ) goto multi_select_end; sqlite3VdbeAddOp2(v, OP_Goto, 0, addrSwap); sqlite3VdbeResolveLabel(v, iBreak); }else |
︙ | ︙ | |||
3005 3006 3007 3008 3009 3010 3011 | return 0; /* Restriction (11) */ } if( isAgg && pSub->pOrderBy ) return 0; /* Restriction (16) */ if( pSub->pLimit && p->pWhere ) return 0; /* Restriction (19) */ if( pSub->pLimit && (p->selFlags & SF_Distinct)!=0 ){ return 0; /* Restriction (21) */ } | | | | 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 | return 0; /* Restriction (11) */ } if( isAgg && pSub->pOrderBy ) return 0; /* Restriction (16) */ if( pSub->pLimit && p->pWhere ) return 0; /* Restriction (19) */ if( pSub->pLimit && (p->selFlags & SF_Distinct)!=0 ){ return 0; /* Restriction (21) */ } if( pSub->selFlags & SF_Recursive ) return 0; /* Restriction (22) */ if( (p->selFlags & SF_Recursive) && pSub->pPrior ) return 0; /* (23) */ /* OBSOLETE COMMENT 1: ** Restriction 3: If the subquery is a join, make sure the subquery is ** not used as the right operand of an outer join. Examples of why this ** is not allowed: ** ** t1 LEFT OUTER JOIN (t2 JOIN t3) |
︙ | ︙ | |||
3589 3590 3591 3592 3593 3594 3595 | Parse *pParse = pWalker->pParse; sqlite3 *db = pParse->db; struct Cte *pCte; assert( pFrom->pTab==0 ); pCte = searchWith(pParse->pWith, pFrom); | | < < < < < < < < < | | > > > > > > > > > | | | > > > | > > | > > > > > > > < < < < | < < < < < < < | 3594 3595 3596 3597 3598 3599 3600 3601 3602 3603 3604 3605 3606 3607 3608 3609 3610 3611 3612 3613 3614 3615 3616 3617 3618 3619 3620 3621 3622 3623 3624 3625 3626 3627 3628 3629 3630 3631 3632 3633 3634 3635 3636 3637 3638 3639 3640 3641 3642 3643 3644 3645 3646 3647 3648 3649 3650 3651 3652 3653 3654 3655 3656 3657 3658 3659 3660 3661 3662 3663 3664 3665 3666 3667 3668 | Parse *pParse = pWalker->pParse; sqlite3 *db = pParse->db; struct Cte *pCte; assert( pFrom->pTab==0 ); pCte = searchWith(pParse->pWith, pFrom); if( pCte ){ ExprList *pEList; Select *pSel; Select *pLeft; /* Left-most SELECT statement */ pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table)); if( pTab==0 ) return WRC_Abort; pTab->nRef = 1; pTab->zName = sqlite3MPrintf(db, "%s", pCte->zName); pTab->iPKey = -1; pTab->nRowEst = 1048576; pTab->tabFlags |= TF_Ephemeral; pFrom->pSelect = sqlite3SelectDup(db, pCte->pSelect, 0); if( db->mallocFailed ) return SQLITE_NOMEM; assert( pFrom->pSelect ); /* Check if this is a recursive CTE. */ pSel = pFrom->pSelect; if( pSel->op==TK_ALL || pSel->op==TK_UNION ){ int i; SrcList *pSrc = pFrom->pSelect->pSrc; for(i=0; i<pSrc->nSrc; i++){ struct SrcList_item *pItem = &pSrc->a[i]; if( pItem->zDatabase==0 && pItem->zName!=0 && 0==sqlite3StrICmp(pItem->zName, pCte->zName) ){ pItem->pTab = pTab; pItem->isRecursive = 1; pTab->nRef++; pSel->selFlags |= SF_Recursive; } } } /* Only one recursive reference is permitted. */ if( pTab->nRef>2 ){ sqlite3ErrorMsg( pParse, "multiple recursive references in cte: %s", pCte->zName ); return WRC_Abort; } assert( pTab->nRef==1 || ((pSel->selFlags&SF_Recursive) && pTab->nRef==2 )); if( ctePush(pParse, pCte) ) return WRC_Abort; sqlite3WalkSelect(pWalker, pTab->nRef==2 ? pSel->pPrior : pSel); for(pLeft=pSel; pLeft->pPrior; pLeft=pLeft->pPrior); pEList = pLeft->pEList; if( pCte->pCols ){ if( pEList->nExpr!=pCte->pCols->nExpr ){ sqlite3ErrorMsg(pParse, "cte \"%s\" returns %d values for %d columns", pCte->zName, pEList->nExpr, pCte->pCols->nExpr ); return WRC_Abort; } pEList = pCte->pCols; } selectColumnsFromExprList(pParse, pEList, &pTab->nCol, &pTab->aCol); if( pSel->selFlags & SF_Recursive ) sqlite3WalkSelect(pWalker, pSel); ctePop(pParse, pCte); } return SQLITE_OK; } #endif |
︙ | ︙ | |||
3711 3712 3713 3714 3715 3716 3717 3718 3719 3720 3721 3722 3723 3724 | /* Look up every table named in the FROM clause of the select. If ** an entry of the FROM clause is a subquery instead of a table or view, ** then create a transient table structure to describe the subquery. */ for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){ Table *pTab; if( pFrom->pTab!=0 ){ /* This statement has already been prepared. There is no need ** to go further. */ assert( i==0 ); return WRC_Prune; } #ifndef SQLITE_OMIT_CTE | > > | 3717 3718 3719 3720 3721 3722 3723 3724 3725 3726 3727 3728 3729 3730 3731 3732 | /* Look up every table named in the FROM clause of the select. If ** an entry of the FROM clause is a subquery instead of a table or view, ** then create a transient table structure to describe the subquery. */ for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){ Table *pTab; assert( pFrom->isRecursive==0 || pFrom->pTab ); if( pFrom->isRecursive ) continue; if( pFrom->pTab!=0 ){ /* This statement has already been prepared. There is no need ** to go further. */ assert( i==0 ); return WRC_Prune; } #ifndef SQLITE_OMIT_CTE |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
2127 2128 2129 2130 2131 2132 2133 | ** enough information about the compound query is known at that point. ** The KeyInfo for addrOpenTran[0] and [1] contains collating sequences ** for the result set. The KeyInfo for addrOpenEphm[2] contains collating ** sequences for the ORDER BY clause. */ struct Select { ExprList *pEList; /* The fields of the result */ | < | 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 | ** enough information about the compound query is known at that point. ** The KeyInfo for addrOpenTran[0] and [1] contains collating sequences ** for the result set. The KeyInfo for addrOpenEphm[2] contains collating ** sequences for the ORDER BY clause. */ struct Select { ExprList *pEList; /* The fields of the result */ u8 op; /* One of: TK_UNION TK_ALL TK_INTERSECT TK_EXCEPT */ u16 selFlags; /* Various SF_* values */ int iLimit, iOffset; /* Memory registers holding LIMIT & OFFSET counters */ int addrOpenEphm[3]; /* OP_OpenEphem opcodes related to this select */ u64 nSelectRow; /* Estimated number of result rows */ SrcList *pSrc; /* The FROM clause */ Expr *pWhere; /* The WHERE clause */ |
︙ | ︙ | |||
2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 | #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 */ #define SF_Values 0x0080 /* Synthesized from VALUES clause */ #define SF_Materialize 0x0100 /* Force materialization of views */ #define SF_NestedFrom 0x0200 /* Part of a parenthesized FROM clause */ #define SF_MaybeConvert 0x0400 /* Need convertCompoundSelectToSubquery() */ /* ** 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 */ | > | 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 | #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 */ #define SF_Values 0x0080 /* Synthesized from VALUES clause */ #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. The ** "SRT" prefix means "SELECT Result Type". */ #define SRT_Union 1 /* Store result as keys in an index */ |
︙ | ︙ | |||
2636 2637 2638 2639 2640 2641 2642 | ** callbacks. */ #define WRC_Continue 0 /* Continue down into children */ #define WRC_Prune 1 /* Omit children but continue walking siblings */ #define WRC_Abort 2 /* Abandon the tree walk */ /* | | < | 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 | ** callbacks. */ #define WRC_Continue 0 /* Continue down into children */ #define WRC_Prune 1 /* Omit children but continue walking siblings */ #define WRC_Abort 2 /* Abandon the tree walk */ /* ** An instance of this structure represents a set of one or more CTEs ** (common table expressions) created by a single WITH clause. */ struct With { int nCte; /* Number of CTEs in the WITH clause */ With *pOuter; /* Containing WITH clause, or NULL */ struct Cte { /* For each CTE in the WITH clause.... */ char *zName; /* Name of this CTE */ ExprList *pCols; /* List of explicit column names, or NULL */ Select *pSelect; /* The definition of this CTE */ struct Cte *pOuterCte; /* Next WITH clause in outer context */ } a[1]; }; /* ** Assuming zIn points to the first byte of a UTF-8 character, ** advance zIn to point to the first byte of the next UTF-8 character. */ |
︙ | ︙ |
Changes to src/vdbe.c.
︙ | ︙ | |||
3366 3367 3368 3369 3370 3371 3372 | } } pCx->isOrdered = (pOp->p5!=BTREE_UNORDERED); break; } #ifndef SQLITE_OMIT_CTE | < < < < < < < < < < < < < < < < < < < < < < < | 3366 3367 3368 3369 3370 3371 3372 3373 3374 3375 3376 3377 3378 3379 | } } pCx->isOrdered = (pOp->p5!=BTREE_UNORDERED); break; } #ifndef SQLITE_OMIT_CTE /* Opcode: SwapCursors P1 P2 * * * ** ** Parameters P1 and P2 are both cursors opened by the OpenEphemeral ** opcode. This opcode deletes the contents of epheremal table P1, ** then renames P2 to P1 and P1 to P2. In other words, following this ** opcode cursor P2 is open on an empty table and P1 is open on the ** table that was initially accessed by P2. |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
5650 5651 5652 5653 5654 5655 5656 | struct SrcList_item *pTabItem; pTabItem = &pTabList->a[pLevel->iFrom]; pTab = pTabItem->pTab; iDb = sqlite3SchemaToIndex(db, pTab->pSchema); pLoop = pLevel->pWLoop; if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ){ | < < < < < < | | 5650 5651 5652 5653 5654 5655 5656 5657 5658 5659 5660 5661 5662 5663 5664 | struct SrcList_item *pTabItem; pTabItem = &pTabList->a[pLevel->iFrom]; pTab = pTabItem->pTab; iDb = sqlite3SchemaToIndex(db, pTab->pSchema); pLoop = pLevel->pWLoop; if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ){ /* Do nothing */ }else #ifndef SQLITE_OMIT_VIRTUALTABLE if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)!=0 ){ const char *pVTab = (const char *)sqlite3GetVTable(db, pTab); int iCur = pTabItem->iCursor; sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0, pVTab, P4_VTAB); }else if( IsVirtual(pTab) ){ |
︙ | ︙ |