Re: INSERT ... ON CONFLICT {UPDATE | IGNORE} 2.0

On Fri, Feb 20, 2015 at 11:34 AM, Heikki Linnakangas
<hlinnakangas(at)vmware(dot)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