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

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

From: David Fetter <david(at)fetter(dot)org>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: Greg Stark <stark(at)enterprisedb(dot)com>,Hitoshi Harada <umi(dot)tanuki(at)gmail(dot)com>,Jeff Davis <pgsql(at)j-davis(dot)com>, Tatsuo Ishii <ishii(at)postgresql(dot)org>,pgsql-hackers(at)postgresql(dot)org
Subject: CYCLE and SEARCH [was Re: Common Table Expressions (WITHRECURSIVE) patch]
Date: 2008-10-04 15:33:21
Message-ID: 20081004153321.GW10944@fetter.org (view raw or flat)
Thread:
Lists: pgsql-hackers
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

In response to

Responses

pgsql-hackers by date

Next:From: Fernando MorenoDate: 2008-10-04 19:12:15
Subject: db_user_namespace, md5 and changing passwords
Previous:From: Robert HaasDate: 2008-10-04 01:39:37
Subject: Re: patch: Add columns via CREATE OR REPLACE VIEW

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