FK's to refer to rows in inheritance child
Hello list,
FK's cannot refer to rows in inheritance childs. With some changes in
LockRows, together with removing the ONLY keyword in ri_trigger.c, it
was possible to refer to the rows in child relations. (WIP patch attached)
Though it passes simple tests, it is far from complete. To our knowledge
the at minimal the following is missing:
1) child relations must be in sync with their parents regarding PK's as
well. What 'in sync' means is probably also open for debate, i.e. what
to propagate or block on ALTER TABLE and how to deal with multiple
inheritance with no unique root parent.
2) uniqueness must be guaranteed not for each individual physical
relation, but for the key in the whole inheritance tree. (how to name
this? global uniqueness?)
3) support for CASCADE actions - currently actions on referenced rows in
child relations are not cascaded.
We're currently figuring if there is consensus on the design approach
for this topic. The wiki mentions these issues
(http://wiki.postgresql.org/wiki/Todo#Inheritance) but must issues
raised seem not to apply anymore.
Issue 1) will probably be straightforward to implement, once there is
consensus how to implement the invariant 'if X, Y are relations and Y is
child of X, then X.x is PK of X iff Y.x is PK of Y' (and there is
consensus that that invariant should hold)
Issue 2) might be less trivial. On our radar is currently
ExecInsertIndexTuples(). When inserting into a relation in an
inheritance chain, also query the other (or all) relations in the chain
for the inserted value, and throw an error when there is a non-empty
result. Instead of constructing an inheritance tree manually in C, it
might be an idea to use SPI in the style of the referential integrity
checks, where the query would be a SELECT on the parent root(s) without
the ONLY keyword, leaving figuring out which relations(indexes) to query
to the inheritance planner.
Any thoughts or ideas are welcomed.
regards,
Yeb Havinga
Willem Dijkstra
Attached is the WIP patch that allows
BEGIN;
CREATE TABLE parent (a int PRIMARY KEY);
CREATE TABLE child (a int PRIMARY KEY) INHERITS (parent);
CREATE TABLE fk (a int REFERENCES parent(a));
END;
INSERT INTO child VALUES (10);
INSERT INTO fk VALUES (10); -- must succeed
INSERT INTO fk VALUES (11); -- should fail
Attachments:
fk_inheritance.v1.patchtext/x-patch; name=fk_inheritance.v1.patchDownload+20-23
Yeb Havinga <yebhavinga@gmail.com> writes:
FK's cannot refer to rows in inheritance childs. With some changes in
LockRows, together with removing the ONLY keyword in ri_trigger.c, it
was possible to refer to the rows in child relations. (WIP patch attached)
Though it passes simple tests, it is far from complete.
Indeed. This isn't even worth the time to review, unless you have a
proposal for fixing the unique-index-across-multiple-tables problem.
regards, tom lane
On 2010-12-01 15:27, Tom Lane wrote:
Yeb Havinga<yebhavinga@gmail.com> writes:
FK's cannot refer to rows in inheritance childs. With some changes in
LockRows, together with removing the ONLY keyword in ri_trigger.c, it
was possible to refer to the rows in child relations. (WIP patch attached)
Though it passes simple tests, it is far from complete.Indeed. This isn't even worth the time to review, unless you have a
proposal for fixing the unique-index-across-multiple-tables problem.
That was in the part that you chose to not quote.
regards,
Yeb Havinga
Yeb Havinga <yebhavinga@gmail.com> writes:
On 2010-12-01 15:27, Tom Lane wrote:
Indeed. This isn't even worth the time to review, unless you have a
proposal for fixing the unique-index-across-multiple-tables problem.
That was in the part that you chose to not quote.
Perhaps I should have said "possibly workable proposal". What you wrote
doesn't even begin to cover the interesting part of the problem, namely
how to ensure uniqueness is preserved in the face of concurrent
insertions.
(My current feelings about this are that a general-purpose solution
would probably cost more than it's worth. What people really care
about is FK to a partitioned table, which is a structure in which
we don't have to solve the general problem: if we know that the
partitioning prevents the same key from appearing in multiple
partitions, then we only have to look into one partition. So this
is just another item that's pending introduction of real partitioning
infrastructure.)
regards, tom lane
On Dec1, 2010, at 15:27 , Tom Lane wrote:
Yeb Havinga <yebhavinga@gmail.com> writes:
FK's cannot refer to rows in inheritance childs. With some changes in
LockRows, together with removing the ONLY keyword in ri_trigger.c, it
was possible to refer to the rows in child relations. (WIP patch attached)Though it passes simple tests, it is far from complete.
Indeed. This isn't even worth the time to review, unless you have a
proposal for fixing the unique-index-across-multiple-tables problem.
I've wondered in the past if a unique index is really necessary on the columns referenced by a FK in all cases, though.
It certainly is the only sane thing to do for For FKs which are marked ON UPDATE/DELETE CASCADE, SET NULL or SET DEFAULT. But couldn't we weaken that requirement for FKs marked ON UPDATE/DELETE NO ACTION or RESTRICT? It seems to me that the current RI code already handles that case quite nicely once "ONLY" is removed from the queries
The only flaw i can see is that INSERTs or UPDATEs on the child table would lock *all* matching parent table rows, which is more than is necessary in theory. But given that solving this would probably require full-fledged predicate locking, I believe this flaw can be lived with. It might be missing something, though...
Another idea might be to allow this if "tableoid" is part of the FK. In that case, unique indices on the remaining columns in the individual child table would be enough to guarantee global uniqueness. For efficiently, you'd probably need to teach the constraint exclusion mechanism that every table has an implicit constraint of the form "tableoid = <the table's oid>". I haven't thought this through, though - so there might be other obstacles as well...
BTW, my "serializable_lock_consisteny" patch would allow you to do this purely within pl/pgsql in a race-condition free way. So if that patch should get applied you might want to consider this as a workaround. Whether it will get applied is yet to be seen, though - currently there doesn't seem to be unanimous vote one way or the other.
best regards,
Florian Pflug
Florian Pflug <fgp@phlo.org> wrote:
BTW, my "serializable_lock_consisteny" patch would allow you to do
this purely within pl/pgsql in a race-condition free way. So if
that patch should get applied you might want to consider this as a
workaround. Whether it will get applied is yet to be seen, though
- currently there doesn't seem to be unanimous vote one way or the
other.
I don't recall seeing any objections to your patch. Do you have a
reference to a post that argues against it?
-Kevin
On Wed, 2010-12-01 at 15:07 +0100, Yeb Havinga wrote:
FK's cannot refer to rows in inheritance childs. With some changes in
LockRows, together with removing the ONLY keyword in ri_trigger.c, it
was possible to refer to the rows in child relations. (WIP patch attached)
This has a userspace solution, which seems preferable technically.
Just have an Object table that is referred to by all parts of the
hierarchy, maintained by triggers. With PK.
CASCADE doesn't work, but then that was an open issue there anyway.
--
Simon Riggs http://www.2ndQuadrant.com/books/
PostgreSQL Development, 24x7 Support, Training and Services
On Dec1, 2010, at 17:11 , Kevin Grittner wrote:
Florian Pflug <fgp@phlo.org> wrote:
BTW, my "serializable_lock_consisteny" patch would allow you to do
this purely within pl/pgsql in a race-condition free way. So if
that patch should get applied you might want to consider this as a
workaround. Whether it will get applied is yet to be seen, though
- currently there doesn't seem to be unanimous vote one way or the
other.I don't recall seeing any objections to your patch. Do you have a
reference to a post that argues against it?
Tom expressed his doubts in http://archives.postgresql.org/pgsql-hackers/2010-05/msg00699.php pretty clearly. He hasn't weighted in since then AFAIK, so I don't know if his objection still stands. But I still figured a word of warning would be indicated, to prevent the OP from relying on my proposed workaround as long as it might still fail to materialize.
best regards,
Florian Pflug
On Dec 1, 2010, at 8:07 AM, Yeb Havinga wrote:
FK's cannot refer to rows in inheritance childs.
We have partially solved this issue at work. In our scenario, we're not using inheritance for partitioning, we're using it for, well, inheriting. As part of that, we have a field in the parent table that tells you what "type" of object each row is, and constraints on the child tables that enforce that. We've created triggers that perform the same operations that the built-in RI triggers do, namely grabbing a share lock on the target row. The difference is that our trigger looks at the "type" field to determine exactly what table it needs to try and grab shared locks on (we need to do this because the backend doesn't allow you to SELECT ... FROM parent FOR SHARE).
Our solution is not complete though. Offhand, I know it doesn't support cascade, but I think there's more stuff it doesn't do. AFAIK all of those shortcomings could be handled with whats available at a user level though, so someone with enough motivation could produce an entire RI framework that worked with inheritance (though the framework would need a way to work around the uniqueness issue).
--
Jim C. Nasby, Database Architect jim@nasby.net
512.569.9461 (cell) http://jim.nasby.net
On 2010-12-01 16:05, Tom Lane wrote:
Perhaps I should have said "possibly workable proposal". What you wrote
doesn't even begin to cover the interesting part of the problem, namely
how to ensure uniqueness is preserved in the face of concurrent
insertions.
The usual page locking done by nbtree doesn't work in this case, since a
conflict can be two inserts into two different indexes. This means that
one way or another, some extra kind of lock is needed. The question is
what current lock mechanism is suitable for this purpose, the answer to
that may depend on the way conflicts are checked for. Checking for
conflicts can be done at row insert time or commit time.
With 'inheritance chain' I mean any set of more than one relation that
is the transitive closure of the inheritance parent and child relation
on a given relation.
- Check at row insert time:
transaction A
-- before insert of row into an inheritance chain, suppose with key value 10
-- lock X exclusively (this is to be a fined grained lock, X could be a
name derived from the inserted key value 10)
-- query inheritance chain for existing values with SnapshotNow
-- on existing value, release 'X locks' taken by current backend and error
-- else normal processing continues (actual insert etc..)
-- after commit, release 'X locks' taken by current backend
If another transaction B wants to insert the same key value 10, it will
block on the lock taken by A, which A releases after commit, then B
continues and when it queries the inheritance chain, it sees the
committed record of A and will then report an error.
The drawback here is lock proliferation: for each row a lock seems unwanted.
- Check at commit time
transaction A
-- inserts row into inheritance chain
-- record row and tuple for later check
-- at commit time, if any check was recorded
--- for every inheritance chain with inserts, ordered by lowest relation oid
---- lock Y exclusively (where Y is a name derived from the inheritance
chain, e.g. lowest relation oid)
---- for every inserted value, query for duplicate key values in
inheritance chain with SnapshotNow
---- on error, release Y and abort transaction (serialization error)
--- after commit / heap tuples marked committed, release all Y locks.transaction B
May insert duplicate values into the inheritance chain, but at commit
time will either get a lock or block on lock. It can continue after A
releases locks, and then it will read the changes committed by B.
Though this solution has fewer locks as the per-row case, a deadlock can
occur if the inheritance chains are not locked in order. This is avoided
by ordering the chains on the lowest oid of its relations. Perhaps the
biggest drawback is that a serialization error must be thrown at commit,
even when the user did not set the transaction isolation level to
SERIALIZABLE and that might violate POLA.
(My current feelings about this are that a general-purpose solution
would probably cost more than it's worth. What people really care
about is FK to a partitioned table, which is a structure in which
we don't have to solve the general problem: if we know that the
partitioning prevents the same key from appearing in multiple
partitions, then we only have to look into one partition. So this
is just another item that's pending introduction of real partitioning
infrastructure.)
While this is true for the partitioning use case, it will never be for
'true' inheritance use cases, and therefore a real partitioning
structure doesn't help the inheritance use cases. (Such as ours that is
a implementation of HL7's reference implementation model.
http://www.hl7.org/v3ballot/html/infrastructure/rim/rim.html) A lot can
be said about object model implementations in relational databases. To
keep it short: Codd stressed the value of the relational model in it's
ACM Turing award lecture: a practical foundation for productivity. It is
not productive, that users must implement foreign key checking in
user-space, instead of using a database primitive.
regards,
Yeb Havinga
On 2010-12-02 11:27, Yeb Havinga wrote:
With 'inheritance chain' I mean any set of more than one relation that
is the transitive closure of the inheritance parent and child relation
on a given relation.
s/transitive closure/transitive reflexive closure
On 2010-12-01 16:58, Florian Pflug wrote:
On Dec1, 2010, at 15:27 , Tom Lane wrote:
Indeed. This isn't even worth the time to review, unless you have a
proposal for fixing the unique-index-across-multiple-tables problem.I've wondered in the past if a unique index is really necessary on the columns referenced by a FK in all cases, though.
Me too, but Tom wrote, in one of the archive threads linked to from the
todo wiki, that it was in the SQL spec, so..
Another idea might be to allow this if "tableoid" is part of the FK. In that case, unique indices on the remaining columns in the individual child table would be enough to guarantee global uniqueness.
Yes that would work, but if the database user must make the tableoid
column, and include in the PK and FK's (i.e. not transparant for the
user), then it would still be a workaround.
BTW, my "serializable_lock_consisteny" patch would allow you to do this purely within pl/pgsql in a race-condition free way. So if that patch should get applied you might want to consider this as a workaround. Whether it will get applied is yet to be seen, though - currently there doesn't seem to be unanimous vote one way or the other.
Thanks for the reference, I will try and see how to use it for this purpose.
regards,
Yeb Havinga
On 2010-12-02 01:18, Jim Nasby wrote:
On Dec 1, 2010, at 8:07 AM, Yeb Havinga wrote:
FK's cannot refer to rows in inheritance childs.
We have partially solved this issue at work. In our scenario, we're not using inheritance for partitioning, we're using it for, well, inheriting. As part of that, we have a field in the parent table that tells you what "type" of object each row is, and constraints on the child tables that enforce that. We've created triggers that perform the same operations that the built-in RI triggers do, namely grabbing a share lock on the target row. The difference is that our trigger looks at the "type" field to determine exactly what table it needs to try and grab shared locks on (we need to do this because the backend doesn't allow you to SELECT ... FROM parent FOR SHARE).
That part is exactly what the current WIP patch takes care of: grabbing
share locks on the right relation.
Our solution is not complete though. Offhand, I know it doesn't support cascade, but I think there's more stuff it doesn't do. AFAIK all of those shortcomings could be handled with whats available at a user level though, so someone with enough motivation could produce an entire RI framework that worked with inheritance (though the framework would need a way to work around the uniqueness issue).
But is 'it can be solved on the user level' enough reason to not
implement it in the server code? Foreign key and unique constraint
checking are features the server should provide.
regards,
Yeb Havinga
On Wed, Dec 1, 2010 at 3:05 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
Perhaps I should have said "possibly workable proposal". What you wrote
doesn't even begin to cover the interesting part of the problem, namely
how to ensure uniqueness is preserved in the face of concurrent
insertions.
I think it wouldn't be very hard to implement "global indexes" which
are just regular indexes that index records from multiple tables. The
index tuple would have to have a relid as well as a ctid. Of course it
would be a lot of work to touch up all the places in the source where
indexes are assumed to reference only one table, and there may be some
tricky parts, but the index itself wouldn't be too hard to implement.
(My current feelings about this are that a general-purpose solution
would probably cost more than it's worth. What people really care
about is FK to a partitioned table, which is a structure in which
we don't have to solve the general problem: if we know that the
partitioning prevents the same key from appearing in multiple
partitions, then we only have to look into one partition. So this
is just another item that's pending introduction of real partitioning
infrastructure.)
I agree 100% here. Global indexes are kind of a check-list item for
Oracle that reassures people that partitioned tables are fully
functional but that people usually end up not wanting to actually use.
They remove a lot of the benefit of having partitioned tables at all.
--
greg
Greg Stark <gsstark@mit.edu> writes:
On Wed, Dec 1, 2010 at 3:05 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
Perhaps I should have said "possibly workable proposal". �What you wrote
doesn't even begin to cover the interesting part of the problem, namely
how to ensure uniqueness is preserved in the face of concurrent
insertions.
I think it wouldn't be very hard to implement "global indexes" which
are just regular indexes that index records from multiple tables. The
index tuple would have to have a relid as well as a ctid. Of course it
would be a lot of work to touch up all the places in the source where
indexes are assumed to reference only one table, and there may be some
tricky parts, but the index itself wouldn't be too hard to implement.
That's been proposed before, and shot down before, though I don't recall
all the reasons offhand. One obvious problem is VACUUM, which assumes
that you can't have two processes trying to vacuum the same index
concurrently. Another is what happens when you drop one of the tables
involved in the index. Even the locking involved to make a uniqueness
check against a different table would be not-nice (locking a table after
you already have lock on its index risks deadlock against operations
going the other way).
regards, tom lane
On 12/04/2010 11:56 AM, Tom Lane wrote:
Greg Stark<gsstark@mit.edu> writes:
[ suggestion for cross-table indexes ]
That's been proposed before, and shot down before, though I don't recall
all the reasons offhand. One obvious problem is VACUUM, which assumes
that you can't have two processes trying to vacuum the same index
concurrently. Another is what happens when you drop one of the tables
involved in the index. Even the locking involved to make a uniqueness
check against a different table would be not-nice (locking a table after
you already have lock on its index risks deadlock against operations
going the other way).
Those are difficulties, certainly. Are they insurmountable obstacles,
though? This is something that has been on the TODO list for ages and I
think is very worth doing, if we can.
cheers
andrew
Andrew Dunstan <andrew@dunslane.net> writes:
Those are difficulties, certainly. Are they insurmountable obstacles,
though? This is something that has been on the TODO list for ages and I
think is very worth doing, if we can.
They're possibly surmountable with enough effort, though I think in
reality what you'd end up with is annoying corner-case behaviors
(eg, deadlock failures in some cases). Anyway Greg and I seem to
agree on the bottom line: such a feature is not actually interesting
for partitioned tables, as it destroys most of the benefits of
partitioning. I have a feeling that the feature will languish on the
TODO list forever, unless someone comes up with a brilliant idea to
avoid the problems. As is, the return on investment to do it just
isn't there.
regards, tom lane
Tom Lane <tgl@sss.pgh.pa.us> writes:
partitioning. I have a feeling that the feature will languish on the
TODO list forever, unless someone comes up with a brilliant idea to
avoid the problems. As is, the return on investment to do it just
isn't there.
That's calling for a try :)
What about a new index type that follows the partitioning scheme in its
root pages in a way that allow the locking to occur in a subpart of it,
rather than for the whole index.
Well, maybe that needs to have an index OID per known partition all
handled into the same physical index for the locking system to work, but
that could mean that indexes would get their objsubid like relations
have their attributes now. It could even be that what we need is a
meta-index and a new kind if index page pointer that would lead to
another physical index.
Oh and that's yet another idea that depends on seeing a partition syntax
supporting current features in core. When will we sketch a plan on that
so that individual hackers interested into a subpart are able to work on
it? I think the last years are telling us that nobody will ever will to
handle it all by himself. Well, or you have to hire Simon :)
Given such an agenda, I'd argue for a feature branch being open for
partitioning so that incremental reviewed work can happen there until we
have enough pieces to consider merging into HEAD.
Regards,
--
Dimitri Fontaine
http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support
On 12/04/2010 01:22 PM, Dimitri Fontaine wrote:
Given such an agenda, I'd argue for a feature branch being open for
partitioning so that incremental reviewed work can happen there until we
have enough pieces to consider merging into HEAD.
Anyone can create a branch and publish it. That's the democracy that git
allows. So if you want it, don't argue for it, just do it.
cheers
andrew
On 2010-12-04 19:22, Dimitri Fontaine wrote:
That's calling for a try :)
What about a new index type that follows the partitioning scheme in its
root pages in a way that allow the locking to occur in a subpart of it,
rather than for the whole index.
Would that (global) index be totally ordered? That seems a prerequisite
for unique constraint checking with _bt_doinsert.
regards,
Yeb Havinga
