Thread: Recursive queries
Are there any plans on implementing support for recursive queries in postgresql in the near future? If so: When? I can see there has been some discussion on the subject in the developer-group for quite some time ago, but aparently all thoughts of recursive queries has been stalled. :-( Regards
On Mon, Jan 24, 2005 at 05:27:46PM +0100, tmp wrote: > Are there any plans on implementing support for recursive queries in > postgresql in the near future? If so: When? > > I can see there has been some discussion on the subject in the > developer-group for quite some time ago, but aparently all thoughts of > recursive queries has been stalled. :-( What do you mean by resursive queries? A query can have a subquery which calls a function which executes another query. That counts as recursion in my book. What type of recursion are you thinking of? Have a nice day, -- Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/ > Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a > tool for doing 5% of the work and then sitting around waiting for someone > else to do the other 95% so you can sue them.
Attachment
Martijn van Oosterhout <kleptog@svana.org> writes:
> What do you mean by resursive queries?
SQL99 "WITH" syntax. See the archives. Andrew Overholt did some work
in this direction a year or so back, but didn't get real far ...
regards, tom lane
On Tue, Jan 25, 2005 at 07:58:33PM +0100, Martijn van Oosterhout wrote: > On Mon, Jan 24, 2005 at 05:27:46PM +0100, tmp wrote: > > Are there any plans on implementing support for recursive queries in > > postgresql in the near future? If so: When? > > > > I can see there has been some discussion on the subject in the > > developer-group for quite some time ago, but aparently all thoughts of > > recursive queries has been stalled. :-( > > What do you mean by resursive queries? A query can have a subquery > which calls a function which executes another query. That counts as > recursion in my book. What type of recursion are you thinking of? The WITH clause in SQL2003 AFAIR (maybe earlier ones as well). -- Alvaro Herrera (<alvherre[@]dcc.uchile.cl>) "Ellos andaban todos desnudos como su madre los parió, y también las mujeres, aunque no vi más que una, harto moza, y todos los que yo vi eran todos mancebos, que ninguno vi de edad de más de XXX años" (Cristóbal Colón)
On Tue, Jan 25, 2005 at 08:24:54PM +0100, tmp wrote: > > What do you mean by resursive queries? A query can have a subquery > > which calls a function which executes another query. That counts as > > recursion in my book. What type of recursion are you thinking of? > > SQL:2003 defines a language construct for recursive queries (T131 and > T132). What I ment with the question was: Will postgresql soon support a > similar (or the same) construct? I don't have the SQL standard but I think you're referring to tables that join to themselves and you want to follow these links recursively. I don't think anybody has written the syntactic sugar, but someone did write a function that provides equivalent output. Have a nice day, -- Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/ > Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a > tool for doing 5% of the work and then sitting around waiting for someone > else to do the other 95% so you can sue them.
Attachment
> What do you mean by resursive queries? A query can have a subquery > which calls a function which executes another query. That counts as > recursion in my book. What type of recursion are you thinking of? No, recursion is a pretty well defined term. See http://en.wikipedia.org/wiki/Recursion SQL:2003 defines a language construct for recursive queries (T131 and T132). What I ment with the question was: Will postgresql soon support a similar (or the same) construct? I know that some Andrew was assigned the task for a year ago, but apparently he has been unsubscribed again. :-(
> I don't think anybody has written the syntactic sugar, but someone did > write a function that provides equivalent output. I think it is important that the funcionality lies in the database engine itself: In that way it can more efficiently make use of the optimizer. Also, I think this "recursive" feature is *the* most important upcoming improvements: Currently there are simply no efficient way of fetching linked structures, which however is quite common in many areas. Regards
In an attempt to throw the authorities off his trail, kleptog@svana.org (Martijn van Oosterhout) transmitted:
> On Mon, Jan 24, 2005 at 05:27:46PM +0100, tmp wrote:
>> Are there any plans on implementing support for recursive queries in
>> postgresql in the near future? If so: When?
>>
>> I can see there has been some discussion on the subject in the
>> developer-group for quite some time ago, but aparently all thoughts of
>> recursive queries has been stalled. :-(
>
> What do you mean by resursive queries? A query can have a subquery
> which calls a function which executes another query. That counts as
> recursion in my book. What type of recursion are you thinking of?
By recursive queries, we mean the form defined in SQL3/SQL.1999.
IBM DB2 uses a syntax like the following; I'd have to rummage around
for extra books to verify standards conformance, but hopefully this
gives the idea...
WITH tmp_rel (object, subobject, quantity) AS
(SELECT part, child_part, quantity FROM
partlist root
WHERE root.part in ('ASSEMBLY 1', 'ASSEMBLY 2', 'ASSEMBLY 3')
UNION ALL
SELECT child.part, child.child_part, child.quantity
FROM partlist child, tmp_rel parent
WHERE parent.subobject = child.part)
SELECT DISTINCT object, subobject, quantity
FROM tmp_rel;
What you add in is the "WITH" clause that lets you define a (possibly
self-referencing) query which you then reference below.
This is more or less equivalent to the "let" clause offered in
languages like Lisp and ML
let disc = (x*x-y*y) in
calculate_with_squares (disc)
calculate_again_with_squares (disc);;
Or
(let ((disc (+ (* x x) (* y y))))
(calculate_with_squares disc)
(calculate_again_with_squares disc))
In Lisp, the thing that allows recursing is, strictly speaking, called
"letrec"...
Nonetheless, the similarity is still quite evident. SQL "WITH" allows
building self-referencing queries, as well as allowing you to better
organize bits that are likely to get reused. If I have some complex
subquery that occurs several times in a query, I might want to use
WITH in a not-so-recursive way to factor out that subquery so it only
needs to be expressed once.
--
output = reverse("gro.gultn" "@" "enworbbc")
http://www.ntlug.org/~cbbrowne/linux.html
"Life. Don't talk to me about life."
-- Marvin the Paranoid Android
On Wed, Jan 26, 2005 at 08:52:37AM -0500, Christopher Browne wrote:
> By recursive queries, we mean the form defined in SQL3/SQL.1999.
>
> IBM DB2 uses a syntax like the following; I'd have to rummage around
> for extra books to verify standards conformance, but hopefully this
> gives the idea...
>
> WITH tmp_rel (object, subobject, quantity) AS
> (SELECT part, child_part, quantity FROM
> partlist root
> WHERE root.part in ('ASSEMBLY 1', 'ASSEMBLY 2', 'ASSEMBLY 3')
> UNION ALL
> SELECT child.part, child.child_part, child.quantity
> FROM partlist child, tmp_rel parent
> WHERE parent.subobject = child.part)
> SELECT DISTINCT object, subobject, quantity
> FROM tmp_rel;
>
> What you add in is the "WITH" clause that lets you define a (possibly
> self-referencing) query which you then reference below.
OMG! While I can understand what you say query does, I simply can't
visualise it at all. Using WITH for named subqueries, that I can
understand, it would even be useful. But self-referencing, I can't even
think of how an executor would even calculate the resultset of the
above query.
There must be some additional constraints, because what happens if I
write a query like:
WITH tmp_rel (num) AS
(SELECT num+1 FROM tmp_rel)
SELECT * FROM tmp_rel;
If I'm understanding you correctly, this query should never complete. I
guess you need to build a query processor smart enough to detect this.
As a base recursive functions should have a seed and an iterator and
the syntax should reflect that. I don't think the WITH syntax is doing
that.
Incidently, for the case people are pointing to recursive queries here,
the contrib/tablefunc module provides an answer with the connectby().
Given the table name, the parent and the child field names it will
return a set resulting from a walk down the tree:
http://developer.postgresql.org/cvsweb.cgi/~checkout~/pgsql/contrib/tablefunc/README.tablefunc?rev=1.11;content-type=text%2Fplain
Anyway, thanks for the info about recurive queries.
Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/
> Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a
> tool for doing 5% of the work and then sitting around waiting for someone
> else to do the other 95% so you can sue them.
Attachment
Check out ltree http://www.sai.msu.su/~megera/postgres/gist/ltree/ On Tue, 25 Jan 2005 22:03:58 +0100, tmp <skrald@amossen.dk> wrote: >> I don't think anybody has written the syntactic sugar, but someone did >> write a function that provides equivalent output. > > I think it is important that the funcionality lies in the database > engine itself: In that way it can more efficiently make use of the > optimizer. > > Also, I think this "recursive" feature is *the* most important upcoming > improvements: Currently there are simply no efficient way of fetching > linked structures, which however is quite common in many areas. > > Regards > > > ---------------------------(end of broadcast)--------------------------- > TIP 9: the planner will ignore your desire to choose an index scan if > your > joining column's datatypes do not match >