Partitioning/inherited tables vs FKs

On May 6, 2010, at 10:52 , Boszormenyi Zoltan wrote:

=# create table parent (id serial primary key, t text);
...
=# create table child () inherits (parent);
...
=# create table refer (id serial primary key, parent_id integer
...
=# insert into child (t) values ('a') returning id;
...
=# select * from parent;
id | t
----+---
1 | a
(1 sor)

=# insert into refer (parent_id) values (1);
ERROR: insert or update on table "refer" violates foreign key
constraint "refer_parent_id_fkey"
DETAIL: Key (parent_id)=(1) is not present in table "parent".

The use case for this was there were different news items,
and there were another table for summaries, that could point
to any of the news items table. Another use case could be
a large partitioned table with an FK to the main table where
the referring table might only contain very few "interesting" data.

Yeah, this is a long-standing issue with inheritance. Table inheritance in postgres isn't much more than an implicit UNION done on selects plus some logic in ALTER TABLE to keep propagate structural changes. Indices and constraints basically always behave as if ONLY had been specified. I'm not even sure if the ids are globally unique in your example - it might be that each child's "id serial" column gets its very own sequence.

One possible workaround is no create a table, say referred_ids, that contains all the ids from parent and all of its children, kept up-to-date via triggers, and point the FK constraint to that table. That also allows for a global unique constraint on the ids by definition a suitable unique or primary key constraint on referred_ids.

What lies at the heart of this problem is the lack of multi-table indices and hence multi-table unique constraints in postgres. AFAIK with those in place the rest amounts to the removal of ONLY from the constraint check queries plus some code to propagate constraint triggers to child tables.

best regards,
Florian Pflug

2010/5/6 Boszormenyi Zoltan <zb@cybertec.at>:

=# insert into refer (parent_id) values (1);
ERROR:  insert or update on table "refer" violates foreign key
constraint "refer_parent_id_fkey"
DETAIL:  Key (parent_id)=(1) is not present in table "parent".

The use case for this was there were different news items,
and there were another table for summaries, that could point
to any of the news items table. Another use case could be
a large partitioned table with an FK to the main table where
the referring table might only contain very few "interesting" data.

No matter what are the semantics, the parent table in the
inheritance chain cannot be used as and endpoint for FKs.

Is it a bug, or intentional?

i would call it a bug, but this is a known issue

The only solution currently is that the referring table has to be
partitioned the same way as the referred table in the FK, and
its parent table has to be queried.

no, you can install a trigger on the child table that verifies the
existence of the id on your partitioned parent table, the SELECT
you'll use inside that trigger will look at the entire set of tables
(as long as you don't use FROM ONLY)

also could be useful to put an index (even a PK) on every child to
ensure uniqueness and make the SELECT more efficient, and of course a
check constraint in every child emulating a partition key

--
Jaime Casanova www.2ndQuadrant.com
Soporte y capacitación de PostgreSQL

On Thu, May 6, 2010 at 6:37 AM, Jaime Casanova <jaime@2ndquadrant.com> wrote:

i would call it a bug, but this is a known issue

The only solution currently is that the referring table has to be
partitioned the same way as the referred table in the FK, and
its parent table has to be queried.

no, you can install a trigger on the child table that verifies the
existence of the id on your partitioned parent table, the SELECT
you'll use inside that trigger will look at the entire set of tables
(as long as you don't use FROM ONLY)

also could be useful to put an index (even a PK) on every child to
ensure uniqueness and make the SELECT more efficient, and of course a
check constraint in every child emulating a partition key

The referential integrity triggers contain some extra magic that isn't
easily simulatable in userland, and that is necessary to make the
foreign key constraints airtight. We've discussed this previously but
I don't remember which thread it was or the details of when things
blow up. I think it's something like this: the parent has a tuple
that is not referenced by any child. Transaction 1 begins, deletes
the parent tuple (checking that it has no children), and pauses.
Transaction 2 begins, adds a child tuple that references the parent
tuple (checking that the parent exists, which it does), and commits.
Transaction 1 commits.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company

Florian Pflug <fgp@phlo.org> writes:

What lies at the heart of this problem is the lack of multi-table
indices and hence multi-table unique constraints in postgres. AFAIK
with those in place the rest amounts to the removal of ONLY from the
constraint check queries plus some code to propagate constraint
triggers to child tables.

Well, the lack of multi-table indexes certainly is the heart of the
problem, but I'm not sure that inventing such a thing is the solution.
Quite aside from the implementation difficulties involved in it,
doing things that way would destroy some of the major reasons to
partition tables at all:

* the index grows as the size of the total data set, it's not limited
by partition size

* can't cheaply drop one partition any more, you have to vacuum the
(big) index first

* probably some other things I'm not thinking of at the moment.

I think the real solution is to upgrade the partitioning infrastructure
so that we can understand that columns are unique across the whole
partitioned table, when the partitioning is done on that column and each
partition has a unique index.

regards, tom lane

On May 6, 2010, at 16:38 , Tom Lane wrote:

Florian Pflug <fgp@phlo.org> writes:

What lies at the heart of this problem is the lack of multi-table
indices and hence multi-table unique constraints in postgres. AFAIK
with those in place the rest amounts to the removal of ONLY from the
constraint check queries plus some code to propagate constraint
triggers to child tables.

Well, the lack of multi-table indexes certainly is the heart of the
problem, but I'm not sure that inventing such a thing is the solution.
Quite aside from the implementation difficulties involved in it,
doing things that way would destroy some of the major reasons to
partition tables at all:

* the index grows as the size of the total data set, it's not limited
by partition size

* can't cheaply drop one partition any more, you have to vacuum the
(big) index first

* probably some other things I'm not thinking of at the moment.

I think the real solution is to upgrade the partitioning infrastructure
so that we can understand that columns are unique across the whole
partitioned table, when the partitioning is done on that column and each
partition has a unique index.

True, for partitioned tables multi-table indices reintroduce some of the performance problems that partitioning is supposed to avoid.

But OTOH if you use table inheritance as a means to map data models (e.g. EER) more naturally to SQL, then multi-table indices have advantages over the partitioning-friendly solution you sketched above.

With a multi-table index, SELECT * FROM PARENT WHERE ID=?? has complexity LOG(N*M) where M is the number of tables inheriting from PARENT (including PARENT itself), and N the average number of rows in these tables. With one index per child, the complexity is M*LOG(N) which is significantly higher if M is large. Constraint exclusion could reduce that to LOG(N), but only if each child is has it's own private ID range which precludes ID assignment from a global sequence and hence makes ID assignment much more complex and error-prone.

Anyway, I was wondering why we need guaranteed uniqueness for FK relationships anyway. Because if we don't (which I didn't check prior to posting this I must admit), then why can't we simply remove the "ONLY" from the RI queries and let ALTER TABLE attach the RI triggers not only to the parent but also to all children. What am I missing?

best regards,
Florian Pflug

Florian Pflug <fgp@phlo.org> writes:

Anyway, I was wondering why we need guaranteed uniqueness for FK
relationships anyway.

It's required by spec, and the semantics aren't terribly sensible
without it.

regards, tom lane

The referential integrity triggers contain some extra magic that isn't
easily simulatable in userland, and that is necessary to make the
foreign key constraints airtight. We've discussed this previously but
I don't remember which thread it was or the details of when things
blow up. I think it's something like this: the parent has a tuple
that is not referenced by any child. Transaction 1 begins, deletes
the parent tuple (checking that it has no children), and pauses.
Transaction 2 begins, adds a child tuple that references the parent
tuple (checking that the parent exists, which it does), and commits.
Transaction 1 commits.

Will SELECT ... FOR SHARE not help?

Regargs,
Dmitry

On Tue, May 11, 2010 at 2:16 AM, Dmitry Fefelov <fozzy@ac-sw.com> wrote:

The referential integrity triggers contain some extra magic that isn't
easily simulatable in userland, and that is necessary to make the
foreign key constraints airtight.  We've discussed this previously but
I don't remember which thread it was or the details of when things
blow up.  I think it's something like this: the parent has a tuple
that is not referenced by any child.  Transaction 1 begins, deletes
the parent tuple (checking that it has no children), and pauses.
Transaction 2 begins, adds a child tuple that references the parent
tuple (checking that the parent exists, which it does), and commits.
Transaction 1 commits.

Will SELECT ... FOR SHARE not help?

Try it, with the example above. I think you'll find that it doesn't.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company

On 2010-05-11 14:29 +0200, Robert Haas wrote:

On Tue, May 11, 2010 at 2:16 AM, Dmitry Fefelov <fozzy@ac-sw.com> wrote:

The referential integrity triggers contain some extra magic that isn't
easily simulatable in userland, and that is necessary to make the
foreign key constraints airtight. We've discussed this previously but
I don't remember which thread it was or the details of when things
blow up. I think it's something like this: the parent has a tuple
that is not referenced by any child. Transaction 1 begins, deletes
the parent tuple (checking that it has no children), and pauses.
Transaction 2 begins, adds a child tuple that references the parent
tuple (checking that the parent exists, which it does), and commits.
Transaction 1 commits.

Will SELECT ... FOR SHARE not help?

Try it, with the example above. I think you'll find that it doesn't.

TXA => delete from foo;
DELETE 1

TXB => select a from foo for share; -- waits

What am I missing?

Regards,
Marko Tiikkaja

2010/5/11 Marko Tiikkaja <marko.tiikkaja@cs.helsinki.fi>:

On 2010-05-11 14:29 +0200, Robert Haas wrote:

On Tue, May 11, 2010 at 2:16 AM, Dmitry Fefelov <fozzy@ac-sw.com> wrote:

The referential integrity triggers contain some extra magic that isn't
easily simulatable in userland, and that is necessary to make the
foreign key constraints airtight.  We've discussed this previously but
I don't remember which thread it was or the details of when things
blow up.  I think it's something like this: the parent has a tuple
that is not referenced by any child.  Transaction 1 begins, deletes
the parent tuple (checking that it has no children), and pauses.
Transaction 2 begins, adds a child tuple that references the parent
tuple (checking that the parent exists, which it does), and commits.
Transaction 1 commits.

Will SELECT ... FOR SHARE not help?

Try it, with the example above.  I think you'll find that it doesn't.

TXA => delete from foo;
DELETE 1

TXB => select a from foo for share; -- waits

What am I missing?

Slightly verbose example of what can go wrong:

CREATE TABLE a (i int PRIMARY KEY);
INSERT INTO a VALUES (1);

CREATE TABLE b (a_id int);

Start with T1:

T1> BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;
BEGIN
T1> SELECT i FROM a WHERE i = 1 FOR SHARE; -- Does a with i = 1 exist?
i
---
1
(1 Zeile)

T1> INSERT INTO b VALUES (1); -- Great, it existed, insert row
pointing to it in b.
INSERT 0 1

Switch to T2:

T2> BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE; -- Evil
transaction T2 is intervening!
BEGIN
T2> SELECT i FROM a WHERE i = 1 FOR SHARE; -- Lock a with i = 1 FOR SHARE.
i
---
1
(1 Zeile)

T2> SELECT a_id FROM b WHERE a_id = 1; -- Check whether it's got
anything pointing to it.
a_id
------
(0 Zeilen)

T2> DELETE FROM a WHERE i = 1; -- Nope, so delete a with i = 1 (this
blocks, because T1 is still holding the lock).

Switch to T1:

1> COMMIT; -- Commit the insertion of a row pointing to a with i = 1
(this releases all locks that T1 is holding).
COMMIT

T2 continues:

DELETE 1
T2> COMMIT; -- Commit the deletion of a with i = 1.
COMMIT
T2> SELECT * FROM b EXCEPT SELECT * FROM a; -- Check for inconsistencies.
a_id
------
1
(1 Zeile)

Woops.

Nicolas

This is getting way off topic, but:

On 5/11/10 3:55 PM +0300, Nicolas Barbier wrote:

T2> SELECT i FROM a WHERE i = 1 FOR SHARE; -- Lock a with i = 1 FOR SHARE.
i
---
1
(1 Zeile)

T2> SELECT a_id FROM b WHERE a_id = 1; -- Check whether it's got
anything pointing to it.
a_id
------
(0 Zeilen)

T2> DELETE FROM a WHERE i = 1; -- Nope, so delete a with i = 1 (this
blocks, because T1 is still holding the lock).

Obviously you wouldn't delete anything with a SHARE lock.

Regards,
Marko Tiikkaja

2010/5/11 Marko Tiikkaja <marko.tiikkaja@cs.helsinki.fi>:

This is getting way off topic, but:

On 5/11/10 3:55 PM +0300, Nicolas Barbier wrote:

T2>  SELECT i FROM a WHERE i = 1 FOR SHARE; -- Lock a with i = 1 FOR
SHARE.
 i
---
 1
(1 Zeile)

T2>  SELECT a_id FROM b WHERE a_id = 1; -- Check whether it's got
anything pointing to it.
 a_id
------
(0 Zeilen)

T2>  DELETE FROM a WHERE i = 1; -- Nope, so delete a with i = 1 (this
blocks, because T1 is still holding the lock).

Obviously you wouldn't delete anything with a SHARE lock.

So where would you put a SELECT ... FOR SHARE to fix the problem? (Per
"Will SELECT ... FOR SHARE not help?".) I agree that my second FOR
SHARE doesn't really make a lot of sense, but that doesn't disprove
the fact that the first FOR SHARE fails to ensure consistency.

Nicolas

On 5/11/10 4:07 PM +0300, Nicolas Barbier wrote:

2010/5/11 Marko Tiikkaja<marko.tiikkaja@cs.helsinki.fi>:

This is getting way off topic, but:

On 5/11/10 3:55 PM +0300, Nicolas Barbier wrote:

T2> SELECT i FROM a WHERE i = 1 FOR SHARE; -- Lock a with i = 1 FOR
SHARE.
i
---
1
(1 Zeile)

T2> SELECT a_id FROM b WHERE a_id = 1; -- Check whether it's got
anything pointing to it.
a_id
------
(0 Zeilen)

T2> DELETE FROM a WHERE i = 1; -- Nope, so delete a with i = 1 (this
blocks, because T1 is still holding the lock).

Obviously you wouldn't delete anything with a SHARE lock.

So where would you put a SELECT ... FOR SHARE to fix the problem? (Per
"Will SELECT ... FOR SHARE not help?".) I agree that my second FOR
SHARE doesn't really make a lot of sense, but that doesn't disprove
the fact that the first FOR SHARE fails to ensure consistency.

I took the "SELECT ... FOR SHARE" suggestion in a more general way,
suggesting the use of row-level locks. T2 should be holding an
exclusive row-level lock (SELECT ... FOR UPDATE) when checking for
references.

Regards,
Marko Tiikkaja

On 5/11/10 4:11 PM +0300, I wrote:

I took the "SELECT ... FOR SHARE" suggestion in a more general way,
suggesting the use of row-level locks. T2 should be holding an
exclusive row-level lock (SELECT ... FOR UPDATE) when checking for
references.

Hmm. Right, that transaction wouldn't see the rows in a serializable
transaction so this doesn't solve the problem.

Regards,
Marko Tiikkaja

Marko Tiikkaja <marko.tiikkaja@cs.helsinki.fi> writes:

On 5/11/10 4:11 PM +0300, I wrote:

I took the "SELECT ... FOR SHARE" suggestion in a more general way,
suggesting the use of row-level locks. T2 should be holding an
exclusive row-level lock (SELECT ... FOR UPDATE) when checking for
references.

Hmm. Right, that transaction wouldn't see the rows in a serializable
transaction so this doesn't solve the problem.

Yeah. The hidden "magic" in the built-in FK code is not locking
(it does actually use SELECT FOR SHARE to lock rows). Rather, it's
about doing tuple liveness checks using snapshots that aren't available
at the SQL level, particularly in serializable transactions.

regards, tom lane

Nicolas Barbier <nicolas.barbier@gmail.com> wrote:

Switch to T1:

1> COMMIT; -- Commit the insertion...
COMMIT

T2 continues:

DELETE 1
T2> COMMIT; -- Commit the deletion of a with i = 1.
COMMIT
T2> SELECT * FROM b EXCEPT SELECT * FROM a;
a_id
------
1
(1 Zeile)

Woops.

This is exactly the sort of issue for which true serializable
behavior will provide a solution. I will be offering a patch to
implement that for 9.1 once 9.0 settles down. FWIW when you commit
T1, the patched code rolls back T2 with this message:

T2> DELETE FROM a WHERE i = 1;
ERROR: could not serialize access due to read/write dependencies
among transactions
HINT: The transaction might succeed if retried.

Thanks for the example; I will it to the others.

-Kevin

On May 11, 2010, at 13:29 , Robert Haas wrote:

On Tue, May 11, 2010 at 2:16 AM, Dmitry Fefelov <fozzy@ac-sw.com> wrote:

The referential integrity triggers contain some extra magic that isn't
easily simulatable in userland, and that is necessary to make the
foreign key constraints airtight. We've discussed this previously but
I don't remember which thread it was or the details of when things
blow up. I think it's something like this: the parent has a tuple
that is not referenced by any child. Transaction 1 begins, deletes
the parent tuple (checking that it has no children), and pauses.
Transaction 2 begins, adds a child tuple that references the parent
tuple (checking that the parent exists, which it does), and commits.
Transaction 1 commits.

Will SELECT ... FOR SHARE not help?

Try it, with the example above. I think you'll find that it doesn't.

That example does in fact work. Here is the precise sequence of commands I tested with constraint checking triggers implemented in PL/PGSQL.

C1: BEGIN
C1: DELETE FROM parent WHERE parent_id = 0
C2: BEGIN
C2: SET TRANSACTION ISOLATION LEVEL SERIALIZABLE -- Optional
C2: INSERT INTO child (parent_id) VALUES (0) -- Waits for C1 to commit
C1: COMMIT -- Now C2 fails either with a constraint_violation or serialization_error

The reason this works is that C2's attempt to SHARE-lock the parent row blocks until C1 commits. In READ COMMITTED mode C2 will then realize that the parent row is now gone. In SERIALIZABLE mode it won't get that far, because the SHARE-locking attempt throws a serialization error since the parent row was concurrently modified.

The serialization error, however, disappears if the two transactions are swapped. The following sequence of commands succeeds, even though the FK constraint is not satisfied.

C1: BEGIN
C1: INSERT INTO child (parent_id) VALUES (0)
C2: BEGIN
C2: SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
C2: SELECT TRUE -- Take snapshot *before* C1 commits
C1: COMMIT
C2: DELETE FROM parent WHERE parent_id = 0 -- Works!
C2: COMMIT

It seems that while SHARE-locking a concurrently deleted row causes a serialization error, deleting a concurrently SHARE-locked is allowed. I do wonder if this shouldn't be considered a bug - whether locks conflict or not does not usually depend on the other in which they are taken.

The build-in constraint triggers avoid the second case by checking not only for rows visible under the transaction's snapshot but also for rows visible under a freshly taken snapshot in the ri_parent PERFORM statement. I do wonder if the recheck was still needed if the DELETE in the second case threw a serialization_error also. Does anyone have an example that proves it necessary?

best regards,
Florian Pflug

Here are the table definitions and trigger functions I used:

CREATE TABLE parent (parent_id SERIAL NOT NULL PRIMARY KEY);
CREATE TABLE child (child_id SERIAL NOT NULL PRIMARY KEY, parent_id INTEGER NOT NULL);

CREATE FUNCTION ri_parent() RETURNS TRIGGER AS $body$
BEGIN
PERFORM TRUE FROM child WHERE parent_id = OLD.parent_id;
IF FOUND THEN
RAISE SQLSTATE '23503' USING MESSAGE = 'Parent ' || OLD.parent_id || ' still referenced during ' || TG_OP;
END IF;
RETURN NULL;
END;
$body$ LANGUAGE PLPGSQL VOLATILE;
CREATE TRIGGER ri_parent AFTER UPDATE OR DELETE ON parent FOR EACH ROW EXECUTE PROCEDURE ri_parent();

CREATE FUNCTION ri_child() RETURNS TRIGGER AS $body$
BEGIN
PERFORM TRUE FROM parent WHERE parent_id = NEW.parent_id FOR SHARE OF parent;
IF NOT FOUND THEN
RAISE SQLSTATE '23503' USING MESSAGE = 'Parent ' || NEW.parent_id || ' does not exist during ' || TG_OP;
END IF;
RETURN NULL;
END;
$body$ LANGUAGE PLPGSQL VOLATILE;
CREATE TRIGGER ri_child AFTER INSERT OR UPDATE ON child FOR EACH ROW EXECUTE PROCEDURE ri_child();

2010/5/11 Florian Pflug <fgp@phlo.org>:

On May 11, 2010, at 13:29 , Robert Haas wrote:

On Tue, May 11, 2010 at 2:16 AM, Dmitry Fefelov <fozzy@ac-sw.com> wrote:

The referential integrity triggers contain some extra magic that isn't
easily simulatable in userland, and that is necessary to make the
foreign key constraints airtight.  We've discussed this previously but
I don't remember which thread it was or the details of when things
blow up.  I think it's something like this: the parent has a tuple
that is not referenced by any child.  Transaction 1 begins, deletes
the parent tuple (checking that it has no children), and pauses.
Transaction 2 begins, adds a child tuple that references the parent
tuple (checking that the parent exists, which it does), and commits.
Transaction 1 commits.

Will SELECT ... FOR SHARE not help?

Try it, with the example above.  I think you'll find that it doesn't.

That example does in fact work. Here is the precise sequence of commands I tested with constraint checking triggers implemented in PL/PGSQL.

[...]

The serialization error, however, disappears if the two transactions are swapped. The following sequence of commands succeeds, even though the FK constraint is not satisfied.

Thanks for figuring this out. I thought there was a case like this
but I couldn't remember exactly how to reproduce it.

C1: BEGIN
C1: INSERT INTO child (parent_id) VALUES (0)
C2: BEGIN
C2: SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
C2: SELECT TRUE -- Take snapshot *before* C1 commits
C1: COMMIT
C2: DELETE FROM parent WHERE parent_id = 0 -- Works!
C2: COMMIT

It seems that while SHARE-locking a concurrently deleted row causes a serialization error, deleting a concurrently SHARE-locked is allowed. I do wonder if this shouldn't be considered a bug - whether locks conflict or not does not usually depend on the other in which they are taken.

Wait - I'm confused. The DELETE in your example happens after C1
commits, so C1 can't still be holding any locks (nor does C2 take any
locks prior to the commit of C1).

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company

Florian Pflug <fgp@phlo.org> wrote:

The serialization error, however, disappears if the two
transactions are swapped. The following sequence of commands
succeeds, even though the FK constraint is not satisfied.

C1: BEGIN
C1: INSERT INTO child (parent_id) VALUES (0)
C2: BEGIN
C2: SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
C2: SELECT TRUE -- Take snapshot *before* C1 commits
C1: COMMIT
C2: DELETE FROM parent WHERE parent_id = 0 -- Works!
C2: COMMIT

Thanks for another good example. Added to serializable test suite.

C2> DELETE FROM parent WHERE parent_id = 0;
ERROR: could not serialize access due to read/write dependencies
among transactions
HINT: The transaction might succeed if retried.
CONTEXT: SQL statement "SELECT TRUE FROM child WHERE parent_id =
OLD.parent_id"
PL/pgSQL function "ri_parent" line 2 at PERFORM

By the way, when adding these, I'm taking off the "FOR SHARE" or
"FOR UPDATE" clauses; they're not needed with true serializable
transactions. Otherwise, examples used as presented.

-Kevin