Greetings hackers! I've renamed the project fsnapshot to pov, PostgreSQL Object Version control system. :)
I've also created a quite nifty SQL command line based utility to perform graph/tree sorting algorithms on data in the database, without the need to export the data to some external application. The utility is named tsort and behaves exactly like the GNU coreutils tool tsort (or the Perl Power Tools tool tcsort). Since tree sorting is a quite common task in computer science, perhaps some of you will find it useful. Source code: https://github.com/gluefinance/pov/blob/master/sql/schema/pov/functions/tsort.pl Also, if I have understood everything correctly, the toposort algorithm in pg_dump_sort.c does not does its best ensuring the objects are created in the same order, if the oids would change or if objects would be dropped/added. The algorithm is probably a simple DFS (depth-first sorting) or BFS (breadth-first sorting) without any effort made to do sorting when selecting the successor objects. It's probably a quite challenging task to implement the extra necessary sorting in C, on top of the standard DFS or BFS algorithm. I put together a small quite nifty plperl utility to do the task, as a simple proof-of-concept and also because I thought it makes sense to provide such a method accessible from the SQL prompt, since tree/graph sorting is probably one of the most commonly performed tasks in many applications dealing. It is quite powerful with all the basic tree sorting features I could think of. I hope you find it useful and perhaps even a bit fun :) Here is a small example on how to use it to analyze pg_depend: create table a ( id int not null, primary key (id)); create table aa ( id int not null, primary key (id), foreign key (id) references a(id)); create table ab ( id int not null, primary key (id), foreign key (id) references a(id)); create table aaa ( id int not null, primary key (id), foreign key (id) references aa(id)); create table aab ( id int not null, primary key (id), foreign key (id) references aa(id)); create table aba ( id int not null, primary key (id), foreign key (id) references ab(id)); create table abb ( id int not null, primary key (id), foreign key (id) references ab(id)); Instead of using oid, one should use unique names for each object (composed differently based on the object type). If doing so, the example below would render exactly the same result even in two databases with completely different oids for the same schema. glue=# select oid,relname from pg_class where relname ~ '^a.?.?$'; oid | relname -------+--------- 52354 | a 52359 | aa 52399 | aba 52369 | ab 52389 | aab 52379 | aaa 52409 | abb (7 rows) Find root objects (source objects, no predecessors), sort numerically: glue=# SELECT tsort(array_to_string(array_agg(distinct objid || ',' || refobjid), ','), ',', 0, 'sub {$a <=> $b}', 'SOURCE') FROM pg_depend; tsort -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------- {0,10939,10940,10942,10943,10945,10946,10948,10949,10951,10952,10955,10956,10958,10959,10962,10963,10966,10967,10970,10971,10973,10974,10976,10977,10980,10981,10983,10984,10985,10986,10988,10989,10991,10992,10994,10995,10998,10999,11001,11002,11004,11005,11008,11009,11011,11012,11014,11015,11018,11019,11021,11022,11024,11025,11028,11029,11031,11032,11034,1103 5,11037,11038,11040,11041,11043,11044,11046,11047,11049,11050,11053,11054,11056,11057,11074,11076,11078,11080,11082,11084,11086,11088,11090,11092,11094,11096,11098,11100,11102,11104,11106,11108,11110,11112,11114,11116,11118,11120,11122,11124,11126,11128,11130,11132,11134,11136,11138,11140,11142,11144,11146,11148,11150,11152,11154,11156,11158,11160,11162,11164, 11166,11168,11170,11172,11174,11176,11178,11180,11182,11184,11186,11188,11190,11192,11193,11194,11195,11196,11197,11198,11199,11200,11201,11202,11203,11204,11205,11206,11207,11208,11209,11210,11211,11212,11214,11216,11218,11220,11222,11224,11226,11228,11230,11232,11234,11236,11238,11240,11241,11242,11243,11244,11245,11246,11247,11248,11249,11250,11251,11252,11 253,11254,11255,11256,11257,11258,11259,11260,11261,11262,11263,11264,11266,11268,11270,11272,11274,11276,11278,11280,11282,11284,11286,11288,11290,11292,11297,11299,11301,11303,11305,11307,11309,11311,11313,11315,11317,11319,11321,11323,11325,11340,11344,11345,11348,11349,11352,11353,11355,11356,11359,11360,11363,11364,11367,11368,11371,11372,11375,11376,1137 9,11380,11383,11384,11387,11388,11391,11392,11395,11396,11398,11399,11402,11403,11405,11406,11409,11410,11413,11414,11417,11418,11421,11422,11425,11426,11429,11430,11433,11434,11437,11438,11441,11442,11444,11445,11448,11450,11451,11453,11455,11456,11458,11460,11461,11463,11465,11466,11468,11470,11471,11473,11475,11476,11478,11480,11481,11483,11484,11487,11488, 11491,11492,11495,11496,11498,11499,11502,11503,11506,11507,11510,11511,11514,11515,11518,11519,11522,11523,11526,11527,11530,11531,11533,11534,11536,11537,11539,11540,11542,11543,11545,11546,11548,11549,11551,11552,11555,11556,52267,52342,52344,52345,52346,52347,52348,52349,52350,52351,52355,52360,52365,52366,52367,52368,52370,52375,52376,52377,52378,52380,52 382,52385,52386,52387,52388,52390,52392,52395,52396,52397,52398,52400,52402,52405,52406,52407,52408,52410,52412,52415,52416,52417,52418} (1 row) Find connected objects to the tables we created above and sort like pg_dump_sort.c (DFS/BFS): glue=# SELECT tsort(array_to_string(array_agg(distinct objid || ',' || refobjid), ','),',',0,'DFS','CONN_INCL','INCLUDE','52354,52359,52399,52369,52389,52379,52409','BOTH') FROM pg_depend; tsort -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------ {52398,52405,52386,52390,52391,52400,52401,52387,52380,52381,52406,52375,52396,52418,52407,52417,52397,52410,52411,52408,52404,52385,52395,52394,52365,52415,52378,52355,52356,52376,52402,52403,52399,52416,52414,52372,52373,52377,52374,52366,52370,52371,52369,52412,52413,52409,52392,52393,52389,52360,52361,52388,52384,52362,52363,52367,52382,52383,52379,52368, 52364,52359,52357,52358,52354,2200} (1 row) Find connected objects to the tables we created above and sort each lexically ascending, preserving the order: glue=# SELECT tsort(array_to_string(array_agg(distinct objid || ',' || refobjid), ','),',',0,'sub {$a cmp $b}','CONN_INCL','INCLUDE','52354,52359,52399,52369,52389,52379,52409','BOTH') FROM pg_depend; tsort -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------ {52355,52356,52360,52361,52365,52366,52367,52368,52364,52370,52371,52375,52376,52377,52378,52374,52357,52358,52354,52380,52381,52382,52383,52385,52386,52387,52388,52384,52379,52390,52391,52392,52393,52395,52396,52397,52398,52394,52362,52363,52359,52389,52400,52401,52402,52403,52405,52406,52407,52408,52404,52399,52410,52411,52412,52413,52415,52416,52417,52418, 52414,52372,52373,52369,52409,2200} (1 row) Calling the utility with no arguments shows the help: glue=# SELECT tsort(); tsort ---------------------------------------------------------------------------------- DESCRIPTION tsort - return a tree's nodes in topological order SYNOPSIS tsort(edges text, delimiter text, debug integer, algorithm text, selection text, operator text, nodes text, direction text); OUTPUT nodes text[] Array of nodes in topologically sorted order INPUT PARAMETERS Parameter Type Regex Description ============================================================================ edges text ^.+$ Node pairs, separated by [delimiter]. delimiter text ^.*$ Node separator in [edges], default is ' ', i.e. single blank space. debug integer Print debug information using RAISE DEBUG: 0 no debug (default) 1 some debug 2 verbose debug algorithm text Sorting algorithm: DFS depth-first (default) explores as far as possible along each branch before backtracking. BFS breadth-first explores all the neighboring nodes, then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on. ^sub sort using perl subroutine. examples: # sort numerically ascending sub {$a <=> $b} # sort numerically descending sub {$b <=> $a} #sort lexically ascending sub {$a cmp $b} # sort lexically descending sub {$b cmp $a} # sort case-insensitively sub {uc($a) cmp uc($b)} For more examples, please goto: http://perldoc.perl.org/functions/sort.html The following options will not affect the order of the nodes in the result, they only control which nodes are included in the result: Parameter Type Regex Description ============================================================================ selection text Selection of nodes, used by [operator]: ALL select all nodes (default) ISOLATED select nodes without any successors nor predecessors SOURCE select nodes with successors but no predecessors SINK select nodes with predecessors but no successors CONN_INCL select nodes connected to [nodes], including [nodes] CONN_EXCL select nodes connected to [nodes], excluding [nodes] separated by [delimiter] operator text Include or exclude nodes in [selection]: INCLUDE include nodes (default) EXCLUDE exclude nodes The following options are only applicable if, [selection] is CONN_INCL or CONN_EXCL Parameter Type Regex Description ============================================================================ nodes text select nodes connected to [nodes] NULL not applicable (default) [nodes] the start nodes, separated by [delimiter] direction text direction to look for connected nodes BOTH traverse both successors and predecessors (default) UP only traverse predecessors DOWN only traverse successors -- Best regards, Joel Jacobson Glue Finance -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
