Thread: Recursive containment of composite types
Bug #5950 proposes the following test case: create table t (); alter table t add childs t; alter table t add id serial not null primary key; Most of the back branches dump core because CheckAttributeType() goes into infinite recursion. That doesn't happen in HEAD, but so far as I can see that's just because of some chance rearrangement of the order of operations in ALTER TABLE. I wouldn't be at all surprised if there are related cases where HEAD fails too. I think the most straightforward and reliable fix for this would be to forbid recursive containment of a rowtype in itself --- ie, the first ALTER should have been rejected. Can anyone think of a situation where it would be sane to allow such a thing? regards, tom lane
On Mon, Mar 28, 2011 at 10:47 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote: > Bug #5950 proposes the following test case: > > create table t (); > alter table t add childs t; > alter table t add id serial not null primary key; > > Most of the back branches dump core because CheckAttributeType() goes > into infinite recursion. That doesn't happen in HEAD, but so far as I > can see that's just because of some chance rearrangement of the order of > operations in ALTER TABLE. I wouldn't be at all surprised if there are > related cases where HEAD fails too. > > I think the most straightforward and reliable fix for this would be to > forbid recursive containment of a rowtype in itself --- ie, the first > ALTER should have been rejected. Can anyone think of a situation where > it would be sane to allow such a thing? Well, essentially what you'd be doing is making a linked list data type. t contains an id, and perhaps also another t. You can travel down through arbitrarily many objects of type t, each of which has an id value, and eventually you'll hit one where t.childs is NULL. So it's semantically sensible, I believe, but it seems perfectly sensible to just prohibit it. If someone wants to do the work to make it work in some future release, we can consider it, but I think there are other aspects of the type system that are more worthy of our attention than this one is. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
On Mon, Mar 28, 2011 at 9:47 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote: > Bug #5950 proposes the following test case: > > create table t (); > alter table t add childs t; > alter table t add id serial not null primary key; > > Most of the back branches dump core because CheckAttributeType() goes > into infinite recursion. That doesn't happen in HEAD, but so far as I > can see that's just because of some chance rearrangement of the order of > operations in ALTER TABLE. I wouldn't be at all surprised if there are > related cases where HEAD fails too. > > I think the most straightforward and reliable fix for this would be to > forbid recursive containment of a rowtype in itself --- ie, the first > ALTER should have been rejected. Can anyone think of a situation where > it would be sane to allow such a thing? Well, maybe. In fact, probably. That's like asking in C if it's sane to have a structure to contain a pointer back to itself, which of course it is. That said, if it doesn't work properly, it should probably be disabled until it does. merlin
On Mon, Mar 28, 2011 at 9:54 AM, Merlin Moncure <mmoncure@gmail.com> wrote: > On Mon, Mar 28, 2011 at 9:47 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote: >> Bug #5950 proposes the following test case: >> >> create table t (); >> alter table t add childs t; >> alter table t add id serial not null primary key; >> >> Most of the back branches dump core because CheckAttributeType() goes >> into infinite recursion. That doesn't happen in HEAD, but so far as I >> can see that's just because of some chance rearrangement of the order of >> operations in ALTER TABLE. I wouldn't be at all surprised if there are >> related cases where HEAD fails too. >> >> I think the most straightforward and reliable fix for this would be to >> forbid recursive containment of a rowtype in itself --- ie, the first >> ALTER should have been rejected. Can anyone think of a situation where >> it would be sane to allow such a thing? > > Well, maybe. In fact, probably. That's like asking in C if it's sane > to have a structure to contain a pointer back to itself, which of > course it is. That said, if it doesn't work properly, it should > probably be disabled until it does. hm, you can work around lack of above at present using two vs one types: postgres=# create table b (); postgres=# create table c (); postgres=# alter table b add c c; postgres=# alter table c add b b; postgres=# alter table c add i int; postgres=# alter table b add j int; postgres=# select row(row(null, 1), 1)::b; row ------------("(,1)",1) This isn't great but might cover some of the cases where you need such a thing (and I tested this on 8.1). merlin
> On Mon, Mar 28, 2011 at 10:47 AM, Tom Lane<tgl@sss.pgh.pa.us> wrote: >> Bug #5950 proposes the following test case: >> >> create table t (); >> alter table t add childs t; >> alter table t add id serial not null primary key; >> >> Most of the back branches dump core because CheckAttributeType() goes >> into infinite recursion. That doesn't happen in HEAD, but so far as I >> can see that's just because of some chance rearrangement of the order of >> operations in ALTER TABLE. I wouldn't be at all surprised if there are >> related cases where HEAD fails too. >> >> I think the most straightforward and reliable fix for this would be to >> forbid recursive containment of a rowtype in itself --- ie, the first >> ALTER should have been rejected. Can anyone think of a situation where >> it would be sane to allow such a thing? > Well, essentially what you'd be doing is making a linked list data > type. t contains an id, and perhaps also another t. You can travel > down through arbitrarily many objects of type t, each of which has an > id value, and eventually you'll hit one where t.childs is NULL. So > it's semantically sensible, I believe, but it seems perfectly sensible > to just prohibit it. This makes me think of HL7 datatypes R1 http://www.hl7.org/v3ballot2011jan/html/welcome/environment/index.html and http://www.hl7.org/v3ballot2011jan/html/infrastructure/datatypes/datatypes.html where a Concept Descriptor type has as attribute a set of concept descriptor types. Regarding the bug: if recursion causes errors, cycles could be dangerous as well. -- Yeb Havinga http://www.mgrid.net/ Mastering Medical Data
Merlin Moncure <mmoncure@gmail.com> writes: >> On Mon, Mar 28, 2011 at 9:47 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote: >>> I think the most straightforward and reliable fix for this would be to >>> forbid recursive containment of a rowtype in itself --- ie, the first >>> ALTER should have been rejected. �Can anyone think of a situation where >>> it would be sane to allow such a thing? >> Well, maybe. In fact, probably. �That's like asking in C if it's sane >> to have a structure to contain a pointer back to itself, which of >> course it is. �That said, if it doesn't work properly, it should >> probably be disabled until it does. > hm, you can work around lack of above at present using two vs one types: > postgres=# create table b (); > postgres=# create table c (); > postgres=# alter table b add c c; > postgres=# alter table c add b b; Well, that'd have to be disallowed too under what I have in mind. Indirect recursion is no safer than direct. If you try alter table b add k serial; at this point, you'll get the same crash or failure as for the direct recursion case. regards, tom lane
On 03/28/2011 11:14 AM, Tom Lane wrote: > Merlin Moncure<mmoncure@gmail.com> writes: >>> On Mon, Mar 28, 2011 at 9:47 AM, Tom Lane<tgl@sss.pgh.pa.us> wrote: >>>> I think the most straightforward and reliable fix for this would be to >>>> forbid recursive containment of a rowtype in itself --- ie, the first >>>> ALTER should have been rejected. Can anyone think of a situation where >>>> it would be sane to allow such a thing? >>> Well, maybe. In fact, probably. That's like asking in C if it's sane >>> to have a structure to contain a pointer back to itself, which of >>> course it is. That said, if it doesn't work properly, it should >>> probably be disabled until it does. >> hm, you can work around lack of above at present using two vs one types: >> postgres=# create table b (); >> postgres=# create table c (); >> postgres=# alter table b add c c; >> postgres=# alter table c add b b; > Well, that'd have to be disallowed too under what I have in mind. > Indirect recursion is no safer than direct. If you try > > alter table b add k serial; > > at this point, you'll get the same crash or failure as for the direct > recursion case. > > I think we should forbid it for now. If someone comes up with a) a good way to make it works and b) a good use case, we can look at it then. I expect the PostgreSQL type system to be a good deal more constrained than a general in-memory programming language type system. If lack of working type recursion were a serious problem surely we'd have seen more squawks about this by now. cheers andrew
Andrew Dunstan <andrew@dunslane.net> writes: > On 03/28/2011 11:14 AM, Tom Lane wrote: >>> I think the most straightforward and reliable fix for this would be to >>> forbid recursive containment of a rowtype in itself --- ie, the first >>> ALTER should have been rejected. Can anyone think of a situation where >>> it would be sane to allow such a thing? > I think we should forbid it for now. If someone comes up with a) a good > way to make it works and b) a good use case, we can look at it then. I > expect the PostgreSQL type system to be a good deal more constrained > than a general in-memory programming language type system. If lack of > working type recursion were a serious problem surely we'd have seen more > squawks about this by now. The immediate issue in CheckAttributeType() could be fixed by tracking which types it was processing and not recursing into an already-open type. Which, not at all coincidentally, is 90% the same code it'll need to have to throw error. The issue for really "making it work" is how do we know if there are any other places that need a recursion defense? I'm pretty sure that find_composite_type_dependencies would, and I don't know where else there might be a hidden assumption that column references don't loop. So I think that it's mostly about testing rather than anything else. If I were fairly confident that I knew where all the risk spots were, I'd just fix them rather than trying to forbid the construction. regards, tom lane
On mån, 2011-03-28 at 09:54 -0500, Merlin Moncure wrote: > Well, maybe. In fact, probably. That's like asking in C if it's sane > to have a structure to contain a pointer back to itself, which of > course it is. But this is not a pointer, it's containment. SQL has pointers, too (reference types).
On Mar 28, 2011, at 10:43 AM, Tom Lane wrote: > Andrew Dunstan <andrew@dunslane.net> writes: >> On 03/28/2011 11:14 AM, Tom Lane wrote: >>>> I think the most straightforward and reliable fix for this would be to >>>> forbid recursive containment of a rowtype in itself --- ie, the first >>>> ALTER should have been rejected. Can anyone think of a situation where >>>> it would be sane to allow such a thing? > >> I think we should forbid it for now. If someone comes up with a) a good >> way to make it works and b) a good use case, we can look at it then. I >> expect the PostgreSQL type system to be a good deal more constrained >> than a general in-memory programming language type system. If lack of >> working type recursion were a serious problem surely we'd have seen more >> squawks about this by now. > > The immediate issue in CheckAttributeType() could be fixed by tracking > which types it was processing and not recursing into an already-open > type. Which, not at all coincidentally, is 90% the same code it'll need > to have to throw error. The issue for really "making it work" is how do > we know if there are any other places that need a recursion defense? > I'm pretty sure that find_composite_type_dependencies would, and I don't > know where else there might be a hidden assumption that column > references don't loop. So I think that it's mostly about testing rather > than anything else. If I were fairly confident that I knew where all > the risk spots were, I'd just fix them rather than trying to forbid the > construction. Perhaps forbid it for now (for safety) but provide the reporter with a patch that would unblock them so they can do furthertesting? The concept is certainly interesting so it'd be nice to support it if we could. It seems like a good fit for things likestoring tree structures. Though, if the type is still hauling around a heap tuple header I think they'll find the performanceof this whole thing to be rather lacking... :( -- Jim C. Nasby, Database Architect jim@nasby.net 512.569.9461 (cell) http://jim.nasby.net