Re: Foreign key quandries

On Sat, 2003-03-01 at 11:06, Stephan Szabo wrote:
> On 1 Mar 2003, Rod Taylor wrote:
>
> > On Sat, 2003-03-01 at 02:38, Stephan Szabo wrote:
> > > On 1 Mar 2003, Rod Taylor wrote:
> > >
> > > > Gah, hit wrong key combination and the email sent early.
> > > >
> > > > Anyway, after that 'sleep' mess at the bottom is:
> > > > T1 or T2: Sleeping too long -- lets run deadlock detection code
> > > > T1 or T2: Kill off random participant of deadlock.
> > > >
> > > > The other participant is then allowed to continue their work.
> > > >
> > > > > Isn't the differentiation going to happen automatically?
> > >
> > > The problem is that in case 2, both tuples 2 and 3 are already removed
> > > before either foreign key check runs, so when T1 adds the value 3
> > > row and checks the pk table it will find that its pk row has been
> > > modified. If the ordering went, delete 2 - check 2, delete 3 - check
> > > 3, this wouldn't be a problem, but then that'd fail in a
> > > spec-non-compliant way if row 2 refered to row 3.
> >
> > The foreign key cascade is explicitly deferred to the end of the
> > statement via the trigger queue, but there is no reason that the foreign
> > key code can't run immediately for each tuple removed.
>
> The problem happens when you have two rows in a table that refer to each
> other with a foreign key to the same table. If both are deleted, it must
> succeed, but it won't if you do the check in between the deletes unless
> I'm missing something. It's effectively the same problem as we currently

In the general case, you're not going to have interdependent tables.
Store a list of tables touched (changed -- not just read) by keys. The
second fkey to touch a table is deferred until the end of the statement
and will have semantics required for that (deadlock in case 2).

So consider a cascade delete from pk tab1 to fk tab2, and pk tab2 to fk
tab1.

tabl -> tab2
tab2 -> tab1

Delete from pk tab1 value in (2, 3)

- Seek tab1, find tuple value 2
- Record tab1 as unsafe
- tab2 fkey doesn't find tab2 on dirty list -- starts work
- Seek tab2, find tuple value 2, cascade delete
- Record tab2 as dirty
- tab1 fkey finds tab1 on dirty list -- defers work
- tab2 fkey finishs scan on tab2 (no more tuples of value 2)
- Seek on tab1 continues, find tuple value 3
- Record tab1 as dirty
- tab2 fkey finds tab2 on dirty list but it was done by the tab2 fkey
(myself) -- so we assume this is a different value (keys are unique) and
safe to deal with
- seek tab2, find tuple value 3, cascade delete
- Record tab2 as dirty
- tab1 fkey finds tab1 on dirty list -- defers work
- tab2 fkey finishs scan on tab2 (no more tuples of value 3)
- seek on tab1 continues -- no more tuples of value 2 or 3

- command counter increment for finished 'delete' on tab1
- deferred (tab2 pk -> tab1 fkey) actions begin execution.
- ...

This *will* deadlock in case 2 as described earlier. But it's no worse
than what we have today -- in fact it's slightly better as one of the
fkeys is fast and clean.

But this is not a common scenario, as it represents a parent <-> child
relationship split between two or more tables. Tuples in two different
tables cross keyed are already deferred for the insert to succeed -- as
such will deadlock by default since checks are deferred until commit.

Whats more interesting is a parent <-> child relationship on a single
table. What you really want to hint at as being dirty is a given pk
value within a table -- but that becomes difficult when multiple foreign
keys on different unique keys are involved.

I think the tree table (parent / child are in same table, making a tree)
also needs to defer it's checks and be susceptible to deadlocks when
involved in a 'case 2' scenario. The accounting required to check for
loops won't be worth it if there are a large number of values --
especially when multiple foreign keys on different unique keys are
involved.

Anyway, the 'checking the constraint too early' problem only exists when
looking at the same tuples and there is a temporary problem. The
solution for the value = value + 1 case in a unique constraint seems to
be to recheck at the end of the statement if there is still a problem.
If there wasn't an issue during the initial index insert, then
everything will be clean later as well.

Fkeys have a slight advantage as they tend to change the table being
scanned, so more work is safe to be done immediately -- but tracking
what has and hasn't been touched in a given CommandCounter will be
important.

> have with the unique constraint (premature checking of the constraint).
> AFAICS, you need to defer to end of statement to get the correct semantics
> out of the checks, or you need to have a state where the rows are sort of
> pseudo-deleted/updated which could be better.
>
--
Rod Taylor <rbt(at)rbt(dot)ca>

PGP Key: http://www.rbt.ca/rbtpub.asc