Re: Problems with approach #2 to value locking (INSERT ... ON CONFLICT UPDATE/IGNORE patch)

On 01/03/2015 02:43 AM, Peter Geoghegan wrote:
> On Thu, Jan 1, 2015 at 11:17 PM, Peter Geoghegan <pg@heroku.com> wrote:
>> I've been working on fixing the bugs that Jeff Janes found [1] with
>> approach #2 to value locking [2]. Approach #1 was unaffected.
>
> Unfortunately, exclusion constraints (which only value locking
> approach #2 has support for, for the IGNORE variant) are broken, even
> with my fix for the largely unrelated issues also described in my
> opening mail. I now believe that it is inherently impossible to
> support exclusion constraints with INSERT ... ON CONFLICT IGNORE, if
> we are insistent that there cannot be livelocks, unprincipled
> deadlocks or spurious exclusion violations....and I think you all know
> how I feel about those  :-)  . I think that we should drop support for
> exclusion constraints, regardless of whatever else happens with value
> locking.
>
> Previously, my mental model of approach #2 was that it more or less
> handled B-Trees and exclusion constraint related indexes equivalently.
> This is untrue, though.
>
> Today, in general, exclusion constraints more or less work by
> physically inserting a heap tuple and index tuple relating to the
> exclusion constraint (typically this is with a GiST index). There
> could well be a conflict due to a concurrent insertion, or even due to
> the fact that there was a conflicting tuple all along. The
> implementation tries to find a conclusively committed conflicting
> tuple. If it does not find such a tuple, it knows that its own already
> physically inserted tuple is enough of a reason for others to have to
> worry about it, and so it may proceed and commit the xact -- once it
> does a whole index scan with only its own tuple found (and not any
> overlapping tuple from an unfinished xact), it's clear that it can
> proceed.
>
> Exclusion constraints are made to do a pre-check by approach #2 to
> value locking, to do an IGNORE, but that isn't really significant
> here. The reason that #2 is broken for exclusion constraints but not
> for unique indexes is that unique index insertion reports a conflict
> in the process of inserting. In contrast, unique constraints insert
> optimistically, and re-check. What's the difference? Well, even though
> (since the implementation passes UNIQUE_CHECK_PARTIAL for unique index
> insertion) we still insert when there is a conflict, there is an
> important distinction: Value locking. That is to say, even though we
> still insert, we also still use buffer locks as value locks in the
> usual way that unique indexes do (we hold an exclusion buffer lock on
> the first B-Tree leaf page the value could be on, as always). We still
> decide that there is no conflict when the is an exclusion buffer lock,
> which is a sufficient choke point to make that determination
> conclusive. This implies that even with many concurrent insertions
> into a newly created table, there will definitely be one inserter that
> conclusively does *not* have a conflict, while the others might
> (depends on the status of the guy who conclusively had *no* conflict,
> or his line of successor xacts that may or may not themselves commit).
>
> In a private e-mail to Heikki, I pointed out that he was mistaken when
> he said that there is a pre-existing problem with exclusion
> constraints: it is not possible for concurrent inserters to both
> spuriously get exclusion violations when only one needs to. Heikki
> accepted this. However, I now realize that Heikki was closer to being
> right about it than I was; you can't get spurious exclusion
> violations, but you can get something that's about the same, which is
> a deadlock. That usually doesn't matter that much, because people
> usually don't worry about the issue with exclusion constraints. But in
> a world where they support INSERT ... ON CONFLICT IGNORE, that isn't
> acceptable, IMV.
>
> I have a test case:
> https://github.com/petergeoghegan/upsert/blob/master/exclusion.sh
>
> I see both spurious exclusion violations, and unprincipled deadlocks
> with this simple IGNORE-based testcase, that uses a GiST + btree_gist
> exclusion constraint. I didn't see livelocks, which would have been
> really bad, because a mutual need to wait on each other's xact causes
> a deadlock, and the deadlock detector detects those. I think that the
> spurious exclusion violations are merely an artifact of the
> implementation, as opposed to an inherent problem with exclusion
> constraints (in other words, I don't withdraw my remarks from the last
> paragraph - only (arguably) unprincipled deadlocks occur with ordinary
> exclusion constraint enforcement with lots of concurrency).

I read this email several times but could not understand. Please explain 
in words of one syllable how the deadlock arises. Then, please find a 
way to fix it.

- Heikki