Skip site navigation (1) Skip section navigation (2)

Re: PostGreSQL and recursive queries...

From: Sam Mason <sam(at)samason(dot)me(dot)uk>
To: pgsql-hackers(at)postgresql(dot)org
Subject: Re: PostGreSQL and recursive queries...
Date: 2007-11-30 19:20:13
Message-ID: 20071130192013.GY1955@frubble.xen.chris-lamb.co.uk (view raw or flat)
Thread:
Lists: pgsql-hackers
 [ 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

In response to

Responses

pgsql-hackers by date

Next:From: Jeff DavisDate: 2007-11-30 20:07:33
Subject: Re: Sorting Improvements for 8.4
Previous:From: Jonah H. HarrisDate: 2007-11-30 18:27:05
Subject: Re: .NET or Mono functions in PG

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group