Re: Common Table Expressions (WITH RECURSIVE) patch - Mailing list pgsql-hackers

On Mon, 2008-09-08 at 18:08 +0100, Andrew Gierth wrote:
>  Jeff> * Mutual Recursion:
> 
> This limitation isn't at all uncommon in other implementations; DB2
> docs for example say:

As with some other things in my list, this doesn't need to be supported
in 8.4. I just wanted to lay out my interpretation of the standard, and
places that we might (currently) fall short of it.

The fact that other DBMSs don't support mutual recursion is a good
indication that it's not important immediately.

>  Jeff>   The standard does not require that the recursive term be on
>  Jeff>   the RHS.
> 
> Again, the standard may not, but existing implementations do:
> 

Again, I don't think we need this for 8.4.

However, I think it's probably more important than mutual recursion.

>  Jeff> * UNION ALL only:
> 
>  Jeff>   with recursive
>  Jeff>     foo(i) as (values(1) union select i+1 from foo where i < 10)
>  Jeff>   select * from foo;
>  Jeff>   ERROR:  non-recursive term and recursive term must be combined with
>  Jeff> UNION ALL
> 
>  Jeff>   The standard seems to allow UNION ALL, UNION, INTERSECT, and
>  Jeff>   EXCEPT (when the recursive term is not on the RHS of the
>  Jeff>   EXCEPT).
> 
> Again, existing implementations disagree. See above for DB2, and for
> MSSQL:
> 

And again, I agree that it's not important for 8.4.

At some point we need to determine what the goalposts are though. Are we
copying existing implementations, or are we implementing the standard?

>  Jeff>   Produces 10 rows of output regardless of what "X" is. This
>  Jeff> should be fixed for 8.4.  Also, this is non-linear recursion,
>  Jeff> which the standard seems to disallow.
> 
> That looks like it should be disallowed somehow.

Agreed. I think it should just throw an error, probably.

> [snip * Strange result with except: which looks like a bug]
> 
>  Jeff> * Aggregates allowed: which
> 
>  Jeff>   with recursive foo(i) as
>  Jeff>     (values(1)
>  Jeff>     union all
>  Jeff>     select max(i)+1 from foo where i < 10)
>  Jeff>   select * from foo;
> 
>  Jeff>   Aggregates should be blocked according to the standard.
>  Jeff>   Also, causes an infinite loop. This should be fixed for 8.4.
> 
> Does the standard require anywhere that non-conforming statements must
> be diagnosed? (seems impractical, since it would forbid extensions)
> 

2.g.iii.4.B explicitly says aggregates should be rejected, unless I have
misinterpreted.

>  
> Yeah, though the standard's use of DISTINCT in this way is something
> of a violation of the POLA.
> 

I agree that's kind of a funny requirement. But that's pretty typical of
the SQL standard. If DB2 or SQL Server follow the standard here, we
should, too. If not, it's open for discussion.

> No. This has already been discussed; it's neither possible nor desirable
> to diagnose all cases which can result in infinite loops, and there are
> important types of queries which would be unnecessarily forbidden.

I didn't say we should forbid all infinite loops. But we should forbid
ones that the standard tells us to forbid.

> Besides, you've misread the spec here: it prohibits the recursive
> reference ONLY on the nullable side of the join. You cite:
> 

Thank you for the correction. It does properly reject the outer joins
that the standard says should be rejected.

>  Jeff> * ORDER BY, LIMIT, and OFFSET are rejected for recursive
>  Jeff> queries. The standard does not seem to say that these should be
>  Jeff> rejected.
> 
> Note that supporting those in subqueries (including CTEs) is a separate
> optional feature of the standard.
> 

I don't feel strongly about this either way, but I prefer that we are
consistent when possible. We do support these things in a subquery, so
shouldn't we support them in all subqueries?

Regards,Jeff Davis