Re: INSERT ... ON CONFLICT {UPDATE | IGNORE} 2.0 - Mailing list pgsql-hackers

On Fri, Feb 20, 2015 at 11:34 AM, Heikki Linnakangas
<hlinnakangas@vmware.com> wrote:
> So, um, are you agreeing that there is no problem? Or did I misunderstand?
> If you see a potential issue here, can you explain it as a simple list of
> steps, please.

Yes. I'm saying that AFAICT, there is no livelock hazard provided
other sessions must do the pre-check (as they must for ON CONFLICT
IGNORE). So I continue to believe that they must pre-check, which you
questioned.

The only real downside here (with not doing the pre-check for regular
inserters with exclusion constraints) is that we can't fix
unprincipled deadlocks for general exclusion constraint inserters
(since we don't want to make them pre-check), but we don't actually
care about that directly. But it also means that it's hard to see how
we can incrementally commit such a fix to break down the patch into
more manageable chunks, which is a little unfortunate.

Hard to break down the problem into steps, since it isn't a problem
that I was able to recreate (as a noticeable livelock). But the point
of what I was saying is that the first phase pre-check allows us to
notice that the one session that got stuck waiting in the second phase
(other conflicters notice its tuple, and so don't insert a new tuple
this iteration).

Conventional insertion with exclusion constraints insert first and
only then looks for conflicts (since there is no pre-check). More
concretely, if you're the transaction that does not "break" here,
within check_exclusion_or_unique_constraint(), and so unexpectedly
waits in the second phase:

+     /*
+      * At this point we have either a conflict or a potential conflict. If
+      * we're not supposed to raise error, just return the fact of the
+      * potential conflict without waiting to see if it's real.
+      */
+     if (violationOK && !wait)
+     {
+         /*
+          * For unique indexes, detecting conflict is coupled with physical
+          * index tuple insertion, so we won't be called for recheck
+          */
+         Assert(!indexInfo->ii_Unique);
+
+         conflict = true;
+         if (conflictTid)
+             *conflictTid = tup->t_self;
+
+         /*
+          * Livelock insurance.
+          *
+          * When doing a speculative insertion pre-check, we cannot have an
+          * "unprincipled deadlock" with another session, fundamentally
+          * because there is no possible mutual dependency, since we only
+          * hold a lock on our token, without attempting to lock anything
+          * else (maybe this is not the first iteration, but no matter;
+          * we'll have super deleted and released insertion token lock if
+          * so, and all locks needed are already held.  Also, our XID lock
+          * is irrelevant.)
+          *
+          * In the second phase, where there is a re-check for conflicts, we
+          * can't deadlock either (we never lock another thing, since we
+          * don't wait in that phase).  However, a theoretical livelock
+          * hazard exists:  Two sessions could each see each other's
+          * conflicting tuple, and each could go and delete, retrying
+          * forever.
+          *
+          * To break the mutual dependency, we may wait on the other xact
+          * here over our caller's request to not do so (in the second
+          * phase).  This does not imply the risk of unprincipled deadlocks
+          * either, because if we end up unexpectedly waiting, the other
+          * session will super delete its own tuple *before* releasing its
+          * token lock and freeing us, and without attempting to wait on us
+          * to release our token lock.  We'll take another iteration here,
+          * after waiting on the other session's token, not find a conflict
+          * this time, and then proceed (assuming we're the oldest XID).
+          *
+          * N.B.:  Unprincipled deadlocks are still theoretically possible
+          * with non-speculative insertion with exclusion constraints, but
+          * this seems inconsequential, since an error was inevitable for
+          * one of the sessions anyway.  We only worry about speculative
+          * insertion's problems, since they're likely with idiomatic usage.
+          */
+         if (TransactionIdPrecedes(xwait, GetCurrentTransactionId()))
+             break;  /* go and super delete/restart speculative insertion */
+     }
+

Then you must successfully insert when you finally "goto retry" and do
another iteration within check_exclusion_or_unique_constraint(). The
other conflicters can't have failed to notice your pre-existing tuple,
and can't have failed to super delete their own tuples before you are
woken (provided you really are the single oldest XID).

Is that any clearer?
-- 
Peter Geoghegan