Re: WITH RECUSIVE patches 0723

> Now we think that we were wrong. This type of query should run into
> infinit recursion and it's user's responsibility that he does not make
> such a query.
>
> Another idea would be prohibiting *any* outer joins in the recursive
> term (DB2 style), but this may be overkill.

Even if you were to do that, I'm pretty sure that you'd find that it
is insufficient to prevent infinite recursion. I suspect it's not
difficult to show that SQL with WITH RECURSIVE is Turing-complete, and
therefore detecting infinite recursion is equivalent to the Halting
problem.

http://en.wikipedia.org/wiki/Halting_problem

Even if it isn't, someone can always call a function written in any of
the procedural languages, which is definitely sufficient to make it
Turing-complete. Then you don't even need WITH RECURSIVE:

rhaas=# create or replace function keep_going() returns setof integer as $$
begin
loop
return next 1;
end loop;
end
$$ language plpgsql;
CREATE FUNCTION
rhaas=# select * from keep_going();
<...>

The way to attack this is by putting in some kind of logic that cuts
the query off when the result-set gets too large or consumes too much
memory or CPU time or something along those lines. Actually detecting
or preventing infinite loops is impossible, and not the real goal
anyway, since a query that generates 10^100 rows is for all practical
purposes just as bad.

...Robert