CYCLE and SEARCH [was Re: Common Table Expressions (WITH RECURSIVE) patch]

On Fri, Oct 03, 2008 at 03:55:56PM -0400, Tom Lane wrote:
> I've successfully taught the WITH patch to do single evaluation of
> WITH queries. I've also been through all of the planner and
> executor code for it and am now feeling pretty happy with the whole
> thing. There are still a small number of loose ends (see XXX in the
> patch), but I don't believe any of them represent significant work
> --- I just left them undone because they weren't in the way of
> testing anything else.

Great!

How hard would it be to add the infrastructure for CYCLE? Here's the
kind of awful hack I've been doing lately in order to detect and
prevent cycles:

CREATE TABLE adjacency(
id INTEGER NOT NULL,
parent_id INTEGER
);

INSERT INTO adjacency VALUES(1,NULL),
(2,1),(3,1),(4,1),
(5,2),(6,2),(7,2),(8,3),(9,3),(10,4),
(11,5),(12,5),(13,6),(14,7),(15,8),
(9,1); /* Cycle! */

WITH RECURSIVE t(node, path) AS (
SELECT id, ARRAY[id]
FROM adjacency
WHERE parent_id IS NULL
UNION ALL
SELECT a1.id, t.path || a1.id
FROM adjacency a1 JOIN t ON (a1.parent_id = t.node)
WHERE a1.id <> ANY(t.path) /* Remove cycle using awful hack :P */
)
SELECT
CASE WHEN array_upper(path,1)>1 THEN '+-' ELSE '' END ||
REPEAT('--', array_upper(path,1)-2) ||
node AS "Branch"
FROM t
ORDER BY path;

I suspect that some kind of hash structure, instantiated only when a
CYCLE clause is specified, could help out with a much, much more
efficient implementation of cycle prevention.

Adding SEARCH will be a lot more complicated, as DEPTH FIRST is
completely different from how the implementation works now. Any ideas
on how this might be approached?

Cheers,
David.
--
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david(dot)fetter(at)gmail(dot)com

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate