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

Search Discussions

  • Dimitri Fontaine at Jan 4, 2011 at 4:51 pm

    Joel Jacobson 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
  • David Fetter at Jan 4, 2011 at 4:53 pm

    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

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
grouppgsql-hackers @
categoriespostgresql
postedJan 4, '11 at 8:30a
activeJan 4, '11 at 4:53p
posts3
users3
websitepostgresql.org...
irc#postgresql

People

Translate

site design / logo © 2022 Grokbase