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(at)sss(dot)pgh(dot)pa(dot)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(at)sss(dot)pgh(dot)pa(dot)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(at)gmail(dot)com> wrote:
> On Mon, Mar 28, 2011 at 9:47 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)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(at)sss(dot)pgh(dot)pa(dot)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(at)gmail(dot)com> writes:
>> On Mon, Mar 28, 2011 at 9:47 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)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(at)gmail(dot)com> writes:
>>> On Mon, Mar 28, 2011 at 9:47 AM, Tom Lane<tgl(at)sss(dot)pgh(dot)pa(dot)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(at)dunslane(dot)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(at)dunslane(dot)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 further testing?

The concept is certainly interesting so it'd be nice to support it if we could. It seems like a good fit for things like storing tree structures. Though, if the type is still hauling around a heap tuple header I think they'll find the performance of this whole thing to be rather lacking... :(
--
Jim C. Nasby, Database Architect jim(at)nasby(dot)net
512.569.9461 (cell) http://jim.nasby.net