Lists: | pgsql-hackers |
---|
From: | Joel Jacobson <joel(at)gluefinance(dot)com> |
---|---|
To: | pgsql-hackers(at)postgresql(dot)org |
Subject: | Implementing pg_dump_sort.c topological sorting in sql/plpgsql/plperl? |
Date: | 2011-01-04 08:29:55 |
Message-ID: | AANLkTik=_OZi0NShedfGHoUOrY6RAdQT3GWgLcjnVyhO@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-hackers |
Hi hackers,
The project I'm currently working with fsnapshot[1], is written in
plain plpgsql and I need to sort all the oids in their
creatable/droppable order.
This has already been properly implemented in pg_dump_sort.c using
Knuth's algorithm for topological sorting, with some special magic to
find and break dependency loops.
It's not possible to use a plain recursive query to do the trick (due
to 'i' bidirectional dependencies and dependency loops).
I need a general approach, only making use of pg_depend.
The function should take no input arguments and the output argument
should be oid[], containing a list of the oids in a
creatable/droppable or order.
It doesn't matter if it is left-to-right, least number of edges first.
Any valid topological sort will do.
I'm sure it's possible to implement it in plpgsql or plperl, but I
wanted to check first if anyone has already made such a function to
hopefully save some time?
Thanks a lot!
[1] https://github.com/gluefinance/fsnapshot
--
Best regards,
Joel Jacobson
Glue Finance
From: | Dimitri Fontaine <dimitri(at)2ndQuadrant(dot)fr> |
---|---|
To: | Joel Jacobson <joel(at)gluefinance(dot)com> |
Cc: | pgsql-hackers(at)postgresql(dot)org |
Subject: | Re: Implementing pg_dump_sort.c topological sorting in sql/plpgsql/plperl? |
Date: | 2011-01-04 16:51:16 |
Message-ID: | 87mxngfw8r.fsf@hi-media-techno.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-hackers |
Joel Jacobson <joel(at)gluefinance(dot)com> writes:
> It's not possible to use a plain recursive query to do the trick (due
> to 'i' bidirectional dependencies and dependency loops).
Well I came up with that while working on some extension related fun
dependency problems, I guess it could help you:
~:5490=# WITH RECURSIVE depends AS (
select 16385 as nsp, objid, refobjid, array[refobjid] as deps
from pg_depend
where refobjid = 16854 and deptype != 'p'
UNION ALL
select p.nsp, p.objid, d.refobjid, deps || d.refobjid
from pg_depend d JOIN depends p ON d.objid = p.objid
where d.deptype != 'p' and not d.refobjid = any(deps)
)
select * from depends;
nsp | objid | refobjid | deps
-------+-------+----------+--------------------
16385 | 16851 | 16854 | {16854}
16385 | 16852 | 16854 | {16854}
16385 | 16853 | 16854 | {16854}
16385 | 16851 | 2200 | {16854,2200}
16385 | 16852 | 2200 | {16854,2200}
16385 | 16852 | 16851 | {16854,16851}
16385 | 16853 | 2200 | {16854,2200}
16385 | 16852 | 2200 | {16854,16851,2200}
16385 | 16852 | 16851 | {16854,2200,16851}
(9 rows)
Regards,
--
Dimitri Fontaine
http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support
From: | David Fetter <david(at)fetter(dot)org> |
---|---|
To: | Joel Jacobson <joel(at)gluefinance(dot)com> |
Cc: | pgsql-hackers(at)postgresql(dot)org |
Subject: | Re: Implementing pg_dump_sort.c topological sorting in sql/plpgsql/plperl? |
Date: | 2011-01-04 16:53:40 |
Message-ID: | 20110104165339.GA25139@fetter.org |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-hackers |
On Tue, Jan 04, 2011 at 09:29:55AM +0100, Joel Jacobson wrote:
> Hi hackers,
>
> The project I'm currently working with fsnapshot[1], is written in
> plain plpgsql and I need to sort all the oids in their
> creatable/droppable order. This has already been properly
> implemented in pg_dump_sort.c using Knuth's algorithm for
> topological sorting, with some special magic to find and break
> dependency loops.
>
> It's not possible to use a plain recursive query to do the trick
> (due to 'i' bidirectional dependencies and dependency loops).
I believe it is possible. I'll try to do it this evening.
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
iCal: webcal://www.tripit.com/feed/ical/people/david74/tripit.ics
Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate