Re: Common Table Expressions (WITH RECURSIVE) patch

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