Re: PostGreSQL and recursive queries...

[ I'm not very sure of my WITH RECURSIVE syntax, so please excuse any
mistakes ]

On Fri, Nov 30, 2007 at 01:00:27PM +0000, Gregory Stark wrote:
> Hopefully at the cte call sites we'll be able to gin up enough information to
> fill in the subquery information enough for the planner above to work with it.
> I could imagine problems the planner would have to deal with though, such as
> what type is "bogon" in this query?
>
> WITH RECURSIVE x(bogon) AS (select bogon from x) select * from x;

That shouldn't be allowed, no types could be deduced. The following
would be allowed though:

WITH RECURSIVE x(bogon) AS (select bogon from x)
select * from x WHERE bogon < 1;

The WHERE clause will constrain bogon to be an INTEGER which can be
unified with everything else, allowing the query to run.

> what about something like:
>
> WITH RECURSIVE x(bogon) AS (select bogon+1 from x) select * from x;

As above, that'll return an integer.

> note that the usual case is something like:
>
> WITH RECURSIVE x(bogon)
> AS (SELECT 1
> UNION ALL
> SELECT bogon+1
> FROM x)
> SELECT *
> FROM x
> WHERE bogon < ?
>
> So the we can't refuse just anything where the types are recursively
> dependent.

Sounds as though you need some sort of type inference algorithm. There
are quite a few decidable ones around, the one by Hindley-Milner being
very popular/common. Decidable means you get the correct answer out in
a reasonable amount of time or it fails, and, barring implementation
bugs, it'll never get stuck trying to figure out what you meant.

> We might have to do something weird like make the types of a
> recursive call "unknown" until it's planned then go back and replan recursive
> queries making use of the new information to catch things like:
>
> create function foo(int) returns text ...
> create function foo(text) returns int ...
>
> with recursive x(bogon)
> as (select 1 union all select foo(bogon) from x)
> select * from x

When would something like the above actually be used in practise?

Supporting things like that would open up a whole bag of undecidable
nastiness (+ associated confusion for the user, when it all goes wrong)
for what I would think is a small increase in expressiveness.

Sam