Thread: Implementing pg_dump_sort.c topological sorting in sql/plpgsql/plperl?

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

Joel Jacobson <joel@gluefinance.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 ALLselect p.nsp, p.objid, d.refobjid, deps || d.refobjid  from pg_depend d JOIN
dependsp 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

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@fetter.org> http://fetter.org/
Phone: +1 415 235 3778  AIM: dfetter666  Yahoo!: dfetter
Skype: davidfetter      XMPP: david.fetter@gmail.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