Re: [HACKERS] pg_depend explained
2011/1/12 Alvaro Herrera alvhe...@commandprompt.com: I think this code should live in the Wiki somewhere: http://wiki.postgresql.org/wiki/Snippets This file contains only the relevant remapping of pg_depend, folding the internal linkages properly: https://github.com/gluefinance/pov/blob/master/sql/schema/pov/views/pg_depend_remapped.sql It can be tested stand-alone and does not require any other components from the pov project. Can I create a wiki snippet myself or do I need some kind of admin access? -- 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
Re: [HACKERS] pg_depend explained
On Fri, Jan 14, 2011 at 09:39, Joel Jacobson j...@gluefinance.com wrote: 2011/1/12 Alvaro Herrera alvhe...@commandprompt.com: I think this code should live in the Wiki somewhere: http://wiki.postgresql.org/wiki/Snippets This file contains only the relevant remapping of pg_depend, folding the internal linkages properly: https://github.com/gluefinance/pov/blob/master/sql/schema/pov/views/pg_depend_remapped.sql It can be tested stand-alone and does not require any other components from the pov project. Can I create a wiki snippet myself or do I need some kind of admin access? Absolutely, no admin access required. As long as you have (or create) a community account, you can edit or create pages. -- Magnus Hagander Me: http://www.hagander.net/ Work: http://www.redpill-linpro.com/ -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] pg_depend explained
On Wed, Jan 12, 2011 at 09:09:31PM +0100, Joel Jacobson wrote: (sorry for top posting, No worries. iPhone + drunk) A dangerous combination indeed. I hear water, NSAIDs and time can help with the hangover ;) pg_depend_before is a select * from pg_depend before creating the test db model Please put a self-contained example on the snippets page, and please also to check that it actually runs before doing so. You'd mangled some aliases in the query you sent, which leads me to believe you hadn't actually tried running it. Cheers, David. -- David Fetter da...@fetter.org http://fetter.org/ Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter Skype: davidfetter XMPP: david.fet...@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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] pg_depend explained
2011/1/13 David Fetter da...@fetter.org: Please put a self-contained example on the snippets page, and please also to check that it actually runs before doing so. You'd mangled some aliases in the query you sent, which leads me to believe you hadn't actually tried running it. I actually hadn't really solved the problem at the time I wrote my last email, it turned out I had to do things a bit differently to avoid running into problems with corner cases. I will put together a self-contained example like you suggested and get back shortly :-) -- 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
Re: [HACKERS] pg_depend explained
2011/1/12 Florian Pflug f...@phlo.org: I suggest you try to node-folding strategy and see how far it gets you. Good suggestion! :-) That's exactly what I've been trying to do, but failed miserably :-( I have written a thorough description of my problem and put it on my github: https://github.com/gluefinance/pov/tree/master/doc In the example, pg_depend.sql, we want to reach the following conclusions in an algorithmic way, only by using pg_depend as in-data: table t1, function f1, sequence s1 have no dependencies, other than the public schema table t2 depends on t1 and table t3 depends on f1 view v1 depends on t1 and view v2 depends on t2 view v3 depends on both v1 and v2 view v4 depends on v3 and f1 The topological tree automatically generated from the data in pg_depend is presented in pg_depend.dot, pg_depend.svg and pg_depend.png. The actual topological tree (possible order of creation) created manually is presented in pg_depend_actual.dot, pg_depend_actual.svg and pg_depend_actual.png. The automatically created objects, such as primary key indexes, constraints and triggers, have been ignored in this graph, as they are implicitly created when creating the base objects. Objective: Define a general algorithm taking ONLY the pg_depend data as input, generating a valid topological directional graph, including at least the nodes in pg_depend_actual.dot, but might as well include all nodes, although it is not necessary, it's certainly won't hurt. It will be necessary to look not only at the nodes (objects) and edges (obj-refobj), but also the deptype for each edge. List of files: pg_depend.sql : A small but sufficient database model of tables, sequences, functions and views. pg_depend.dot : Digraph in DOT language (plaintext format), generated automatically only by using data from pg_data. pg_depend.png : PNG generated using GraphViz with pg_depend.dot as input pg_depend.svg : SVG generated using GraphViz with pg_depend.dot as input pg_depend_actual.dot : Digraph in DOT language (plaintext format), generated manually, shows the actual possible order of creation, only including the base objects. pg_depend_actual.png : PNG generated using GraphViz with pg_depend_actual.dot as input pg_depend_actual.svg : SVG generated using GraphViz with pg_depend_actual.dot as input -- 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
Re: [HACKERS] pg_depend explained
Excerpts from Joel Jacobson's message of mié ene 12 07:07:35 -0300 2011: The automatically created objects, such as primary key indexes, constraints and triggers, have been ignored in this graph, as they are implicitly created when creating the base objects. FWIW this idea fails when you consider stuff such as circular foreign keys (and I suppose there are other, more common cases). If you really want something general you need to break those apart. (This is the explanation for the “break the loop” code in pg_dump I imagine) -- Álvaro Herrera alvhe...@commandprompt.com The PostgreSQL Company - Command Prompt, Inc. PostgreSQL Replication, Consulting, Custom Development, 24x7 support -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] pg_depend explained
2011/1/12 Alvaro Herrera alvhe...@commandprompt.com: FWIW this idea fails when you consider stuff such as circular foreign keys (and I suppose there are other, more common cases). If you really want something general you need to break those apart. (This is the explanation for the “break the loop” code in pg_dump I imagine) Good point. Yes, the algorithm must be able to break the loop, i.e. remove the edges causing the loops. This has already been properly solved in pg_dump, but I frankly don't really understand exactly how this is done, at least not the general rule on how to do it, even after spending hours studying the source code. Also, circular dependencies seems impossible for some object classes, such as functions, views, constraints and triggers. None of them can possibly refer to them self. If you only need to create/drop objects of these classes (like in my case within the pov-project), it's not important to break the loop in a clever way, i.e. simply removing any of the edges, not necessarily the best suited one, will do for my purpose. I have updated the example with two circular relations: -- Circular dependencies: CREATE TABLE tselfref ( id int not null PRIMARY KEY, parentid int not null REFERENCES tselfref(id) ); CREATE TABLE tcircular ( id int not null PRIMARY KEY, id2 int not null REFERENCES tselfref(id) ); ALTER TABLE tselfref ADD COLUMN id2 int not null REFERENCES tcircular ( id ); I have also updated pd_depend.[sql|dot|png|svg] and pg_depend_actual.[dot|png|svg] with the circular references. The dotted edges in pg_depend_actual are the edges which must be removed to break the loop. Any ideas on how to design an algorithm to transform the digraph pg_depend into pg_depend_actual are highly appreciated. -- 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
Re: [HACKERS] pg_depend explained
Joel Jacobson j...@gluefinance.com writes: Also, circular dependencies seems impossible for some object classes, such as functions, views, constraints and triggers. regression=# create table tt(f1 int, f2 int); CREATE TABLE regression=# create view v1 as select * from tt; CREATE VIEW regression=# create view v2 as select * from v1; CREATE VIEW regression=# create or replace view v1 as select * from v2; CREATE VIEW regression=# drop view v1; ERROR: cannot drop view v1 because other objects depend on it DETAIL: view v2 depends on view v1 HINT: Use DROP ... CASCADE to drop the dependent objects too. regression=# drop view v2; ERROR: cannot drop view v2 because other objects depend on it DETAIL: view v1 depends on view v2 HINT: Use DROP ... CASCADE to drop the dependent objects too. This isn't particularly *useful*, maybe, but it's hardly impossible. And if we analyzed function dependencies in any detail, circular dependencies among functions would be possible (and useful). regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] pg_depend explained
2011/1/12 Tom Lane t...@sss.pgh.pa.us: This isn't particularly *useful*, maybe, but it's hardly impossible. And if we analyzed function dependencies in any detail, circular dependencies among functions would be possible (and useful). Thanks Tom for clarifying, this makes me even more motivated into implementing the creation order-algorithm using only sql/plpgsql and pg_depend. If you have any ideas on how to do this, in addition to reading the dependency.c and pg_dump_sort.c source code, they would be highly appreciated. Any tips on articles on graph algorithms which not only take edges (node-node) as indata, but also a edge type as indata (i.e. the deptype in pg_depend) would also be very useful. I have only found algorithms to do sorting on normal directional graphs, where all edges are threated the same. -- 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
Re: [HACKERS] pg_depend explained
Joel Jacobson j...@gluefinance.com writes: 2011/1/12 Tom Lane t...@sss.pgh.pa.us: This isn't particularly *useful*, maybe, but it's hardly impossible. And if we analyzed function dependencies in any detail, circular dependencies among functions would be possible (and useful). Thanks Tom for clarifying, this makes me even more motivated into implementing the creation order-algorithm using only sql/plpgsql and pg_depend. If you have any ideas on how to do this, in addition to reading the dependency.c and pg_dump_sort.c source code, they would be highly appreciated. I've sometimes found it useful to think of internal dependencies as acting like normal dependencies pointing in the other direction. I'm not sure that would do much to solve your problem, but it might be worth trying. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] pg_depend explained
On Wed, Jan 12, 2011 at 2:06 PM, Joel Jacobson j...@gluefinance.com wrote: Tom, you are a genious! No, seriously, I mean it, this is awesome, it worked! YES! You totally saved my day! Thank you! Finally! I'm so happy! :-) :-) :-) stage whisper Hey, guys, I think it worked...! -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] pg_depend explained
Excerpts from Joel Jacobson's message of mié ene 12 16:06:24 -0300 2011: The query below can both produce a DOT-format graph and a tsort of the creatable order of objects: WITH NewObjectOids AS ( SELECT * FROM pg_depend WHERE deptype 'p' EXCEPT SELECT * FROM pg_depend_before ), I think this code should live in the Wiki somewhere: http://wiki.postgresql.org/wiki/Snippets -- Álvaro Herrera alvhe...@commandprompt.com The PostgreSQL Company - Command Prompt, Inc. PostgreSQL Replication, Consulting, Custom Development, 24x7 support -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] pg_depend explained
On Wed, Jan 12, 2011 at 08:06:24PM +0100, Joel Jacobson wrote: 2011/1/12 Tom Lane t...@sss.pgh.pa.us: I've sometimes found it useful to think of internal dependencies as acting like normal dependencies pointing in the other direction. I'm not sure that would do much to solve your problem, but it might be worth trying. Tom, you are a genious! No, seriously, I mean it, this is awesome, it worked! YES! You totally saved my day! Thank you! Finally! I'm so happy! :-) :-) :-) This was the little piece of code: CASE WHEN DepType ~ '^(a|ni|in|an|na)$' THEN --- Swap edges ELSE -- Do not swap edges END Look at the attached svg graph how beautiful the automatically generated graph look like now! :-) The tsort of the objects now sort all the normal objects in a creatable order! Here is the result of the tsort (only including the normal objects (the one I care about (I don't have to create the internal/auto objects, nor drop them))): The query below can both produce a DOT-format graph and a tsort of the creatable order of objects: WITH NewObjectOids AS ( SELECT * FROM pg_depend WHERE deptype 'p' EXCEPT SELECT * FROM pg_depend_before To what does pg_depend_before refer? Cheers, David. -- David Fetter da...@fetter.org http://fetter.org/ Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter Skype: davidfetter XMPP: david.fet...@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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] pg_depend explained
(sorry for top posting, iPhone + drunk) pg_depend_before is a select * from pg_depend before creating the test db model Sent from my iPhone On 12 jan 2011, at 20:36, David Fetter da...@fetter.org wrote: On Wed, Jan 12, 2011 at 08:06:24PM +0100, Joel Jacobson wrote: 2011/1/12 Tom Lane t...@sss.pgh.pa.us: I've sometimes found it useful to think of internal dependencies as acting like normal dependencies pointing in the other direction. I'm not sure that would do much to solve your problem, but it might be worth trying. Tom, you are a genious! No, seriously, I mean it, this is awesome, it worked! YES! You totally saved my day! Thank you! Finally! I'm so happy! :-) :-) :-) This was the little piece of code: CASE WHEN DepType ~ '^(a|ni|in|an|na)$' THEN --- Swap edges ELSE -- Do not swap edges END Look at the attached svg graph how beautiful the automatically generated graph look like now! :-) The tsort of the objects now sort all the normal objects in a creatable order! Here is the result of the tsort (only including the normal objects (the one I care about (I don't have to create the internal/auto objects, nor drop them))): The query below can both produce a DOT-format graph and a tsort of the creatable order of objects: WITH NewObjectOids AS ( SELECT * FROM pg_depend WHERE deptype 'p' EXCEPT SELECT * FROM pg_depend_before To what does pg_depend_before refer? Cheers, David. -- David Fetter da...@fetter.org http://fetter.org/ Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter Skype: davidfetter XMPP: david.fet...@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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] pg_depend explained
Joel Jacobson j...@gluefinance.com writes: Has anyone written a in-depth description on how to traverse the pg_depend tree? Try reading the code in src/backend/catalog/dependency.c. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] pg_depend explained
2011/1/11 Tom Lane t...@sss.pgh.pa.us: Try reading the code in src/backend/catalog/dependency.c. I've tried but failed to figure it out anyway. The focus in dependency.c is to find out dependencies of a given object. What I want to do is something slighly different. I need to figure out the order of creation of all objects, not just the dependencies for a single object. Basically, I want to do order by oid, but since you cannot trust the oid order (like we did in pre-7.3), I need to get the sorted list using pg_depend somehow. I guess I could make findDependentObjects() callable from sql and call it for each and every object, but that's a quite big project, I was hoping it was possible to do it in plain sql, or at least only by relying on plpgsql/plperl. I've implemented tsort() in plperl, but that didn't really help me much, since you need to jump around in the tree when you encounter 'internal' and 'auto' nodes. My last resort is to sort by oid, but I really don't want to do that since it would render the entire solution unreliable and I would never feel comfortable using it in the production environment. This is the last component I need in order to complete the work on the pov-project http://www.github.com/gluefinance/pov I would highly appreciate your help, I feel a bit lame since I've spent over two days working on this. It's not difficult if you are allowed to build specialized queries for each class, but my goal is a general query only relying on pg_depend. -- 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
Re: [HACKERS] pg_depend explained
Joel Jacobson j...@gluefinance.com writes: I need to figure out the order of creation of all objects, not just the dependencies for a single object. In that case try pg_dump's pg_dump_sort.c. You will never get the order of creation of objects, because that isn't tracked; but you can find out what a safe order would be. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] pg_depend explained
On Jan11, 2011, at 16:54 , Joel Jacobson wrote: Has anyone written a in-depth description on how to traverse the pg_depend tree? The 'a' and 'i' deptype really makes it hard to figure out the dependency order, a topological sort does not work. Could you give an example of the kind of trouble you're experiencing trying to use a topological sort? best regards, Florian Pflug -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] pg_depend explained
2011/1/11 Florian Pflug f...@phlo.org: Could you give an example of the kind of trouble you're experiencing trying to use a topological sort? Let's say you have a table t and a view v. The view v is defined as select * from t; If we put all objects in a tree, with the public schema as the root, both v and t will directly under the root, but in reality, v cannot be created before t. This is the reason why a normal topological sort doesn't work. You have to look at the deptype and sort nodes having internal edges between them differently. The pg_dump source code of course contains all the logic necessary to do the trick, but it's not that easy to follow. I guess it's time for plan B, sorting based on oid, no biggie, it will work for my purpose, but it's damn ugly. -- 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
Re: [HACKERS] pg_depend explained
On Jan11, 2011, at 23:55 , Joel Jacobson wrote: 2011/1/11 Florian Pflug f...@phlo.org: Could you give an example of the kind of trouble you're experiencing trying to use a topological sort? Let's say you have a table t and a view v. The view v is defined as select * from t; If we put all objects in a tree, with the public schema as the root, both v and t will directly under the root, but in reality, v cannot be created before t. AFAICS, you get the following dependencies (apart from the obvious NORMAL dependencies from the pg_class entries of t and v on public) t (pg_class) --[INTERNAL]-- t (pg_type) /°\ | [NORMAL] | _RETURN (pg_rewrite) || [NORMAL] [INTERNAL] || \./ \./ v (pg_class) --[INTERNAL]-- v (pg_type) INTERNAL dependencies mark objects which spring into existence once the referenced (target in my diagram) object is created. You can thus fold a node I (the INTERNALly-depending object) into a node O (the object created by the user) if there is an INTERNAL dependency from I to O. The diagram then becomes v (pg_class) --[NORMAL]-- t (pg_class) Which correctly states that t must be created before v. This is the reason why a normal topological sort doesn't work. You have to look at the deptype and sort nodes having internal edges between them differently. I suggest you try to node-folding strategy and see how far it gets you. I guess it's time for plan B, sorting based on oid, no biggie, it will work for my purpose, but it's damn ugly. That will probably crash and burn once the OIDs have wrapped around once. best regards, Florian Pflug -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
