Re: INSERT...ON DUPLICATE KEY LOCK FOR UPDATE

On Mon, Nov 18, 2013 at 6:44 AM, Heikki Linnakangas
<hlinnakangas(at)vmware(dot)com> wrote:
> I think it's important to recap the design goals of this.

Seems reasonable to list them out.

> * It should be usable and perform well for both large batch updates and
> small transactions.

I think that that's a secondary goal, a question to be considered but
perhaps deferred during this initial effort. I agree that it certainly
is important.

> * It should perform well both when there are no duplicates, and when there
> are lots of duplicates

I think this is very important.

> And from that follows some finer requirements:
>
> * Performance when there are no duplicates should be close to raw INSERT
> performance.
>
> * Performance when all rows are duplicates should be close to raw UPDATE
> performance.
>
> * We should not leave behind large numbers of dead tuples in either case.

I agree with all that.

> Anything else I'm missing?

I think so, yes. I'll add:

* Should not deadlock unreasonably.

If the UPDATE case is to work and perform almost as well as a regular
UPDATE, that must mean that it has essentially the same
characteristics as plain UPDATE. In particular, I feel fairly strongly
that it is not okay for upserts to deadlock with each other unless the
possibility of each transaction locking multiple rows (in an
inconsistent order) exists. I don't want to repeat the mistakes of
MySQL here. This is a point that I stressed to Robert on a previous
occasion [1]. It's why value locks and row locks cannot be held at the
same time. Incidentally, that implies that all alternative schemes
involving bloat will bloat once per attempt, I believe.

I'll also add:

* Should anticipate a day when Postgres needs plumbing for SQL MERGE,
which is still something we want, particularly for batch operations. I
realize that the standard doesn't strictly require MERGE to handle the
concurrency issues, but even still I don't think that an
implementation that doesn't is practicable - does such an
implementation currently exist in any other system?

> What about exclusion constraints? I'd like to see this work for them as
> well. Currently, exclusion constraints are checked after the tuple is
> inserted, and you abort if the constraint was violated. We could still
> insert the heap and index tuples first, but instead of aborting on
> violation, we would kill the heap tuple we already inserted and retry. There
> are some complications there, like how to wake up any other backends that
> are waiting to grab a lock on the tuple we just killed, but it seems doable.

I agree that it's at least doable.

> That would, however, perform badly and leave garbage behind if there are
> duplicates. A refinement of that would be to first check for constraint
> violations, then insert the tuple, and then check again. That would avoid
> the garbage in most cases, but would perform much more poorly when there are
> no duplicates, because it needs two index scans for every insertion. A
> further refinement would be to keep track of how many duplicates there have
> been recently, and switch between the two strategies based on that.

Seems like an awful lot of additional mechanism.

> That cost of doing two scans could be alleviated by using markpos/restrpos
> to do the second scan. That is presumably cheaper than starting a whole new
> scan with the same key. (markpos/restrpos don't currently work for non-MVCC
> snapshots, so that'd need to be fixed, though)

Well, it seems like we could already use a "pick up where you left
off" mechanism in the case of regular btree index tuple insertions
into unique indexes -- after all, we don't do that in the event of
blocking pending the outcome of the other transaction (that inserted a
duplicate that we need to conclusively know has or has not committed)
today. The fact that this doesn't already exist leaves me less than
optimistic about the prospect of making it work to facilitate a scheme
such as the one you describe here. (Today we still need to catch a
committed version of the tuple that would make our tuple a duplicate
from a fresh index scan, only *after* waiting for a transaction to
commit/abort at the end of our original index scan). So we're already
pretty naive about this, even though it would pay to not be.

Making something like markpos work for the purposes of an upsert
implementation seems not only hard, but also like a possible
modularity violation. Are we not unreasonably constraining the
implementation going forward? My patch respects the integrity of the
am abstraction, and doesn't really add any knowledge to the core
system about how amcanunique index methods might go about implementing
the new "amlock" method. The core system worries a bit about the "low
level locks" (as it naively refers to value locks), and doesn't
consider that it has the right to hold on to them for more than an
instant, but that's about it. Plus we don't have to worry about
whether something does or does not work for a certain snapshot type
with my approach, because as with the current unique index btree
coding, it operates at a lower level than that, and does not need to
consider visibility as such.

The markpos and restpos am methods only called for regular index
(only) scans, that don't need to worry about things that are not
visible. Of course, upsert needs to worry about
invisible-but-conclusively-live things. This seems much harder, and
basically implies value locking of some kind, if I'm not mistaken. So
have you really gained anything?

So what I've done, aside from being, as you say below, close to
optimal, is in a sense defined in terms of existing, well-established
abstractions. I feel it's easier to reason about the implications of
holding value locks (whatever the implementation) for longer and
across multiple operations than it is to do all this instead. What
I've done with locking is scary, but not as scary as the worst case of
alternative implementations.

> And that detour with exclusion constraints takes me back to the current
> patch :-). What if you implemented the unique check in a similar fashion too
> (when doing INSERT ON DUPLICATE KEY ...)? First, scan for a conflicting key,
> and mark the position. Then do the insertion to that position. If the
> insertion fails because of a duplicate key (which was inserted after we did
> the first scan), mark the heap tuple as dead, and start over. The indexam
> changes would be quite similar to the changes you made in your patch, but
> instead of keeping the page locked, you'd only hold a pin on the target page
> (if even that). The first indexam call would check that the key doesn't
> exist, and remember the insert position. The second call would re-find the
> previous position, and insert the tuple, checking again that there really
> wasn't a duplicate key violation. The locking aspects would be less scary
> than your current patch.
>
> I'm not sure if that would perform as well as your current patch. I must
> admit your current approach is pretty optimal performance-wise. But I'd like
> to see it, and that would be a solution for exclusion constraints in any
> case.

I'm certainly not opposed to making something like this work for
exclusion constraints. Certainly, I want this to be as general as
possible. But I don't think that it needs to be a blocker, and I don't
think we gain anything in code footprint by addressing that by being
as general as possible in our approach to the basic concurrency issue.
After all, we're going to have to repeat the basic pattern in multiple
modules.

With exclusion constraints, we'd have to worry about a single slot
proposed for insertion violating (and therefore presumably obliging us
to lock) every row in the table. Are we going to have a mechanism for
spilling a tid array potentially sized in gigabytes to disk (relating
to just one slot proposed for insertion)? Is it principled to have
that one slot project out rejects consisting of (say) the entire
table? Is it even useful to lock multiple rows if we can't really
update them, because they'll overlap each other when all updated with
the one value? These are complicated questions, and frankly I don't
have the bandwidth to answer them too soon. I just want to implement a
feature that there is obviously huge pent up demand for, that has in
the past put Postgres at a strategic disadvantage. I don't think it is
unsound to define ON DUPLICATE KEY in terms of unique indexes. That's
how we represent uniques...it isn't spelt ON OVERLAPPING or whatever.
That seems like an addition, a nice-to-have, and maybe not even that,
because exclusion-constrained columns *aren't* keys, and people aren't
likely to want to upsert details of a booking (the typical exclusion
constraint use-case) with the booking range in the UPDATE part's
predicate. They'd just do it by key, because they'd already have a
booking number PK value or whatever.

Making this perform as well as possible is an important consideration.
All alternative approaches that involve bloat concern me, and for
reasons that I'm not sure were fully appreciated during earlier
discussion on this thread: I'm worried about the worst case, not the
average case. I am worried about a so-called "thundering herd"
scenario. You need something like LockTuple() to arbitrate ordering,
which seems complex, and like a further modularity violation. If this
is to perform well when there are lots of existing tuples to be
updated (with contention that wouldn't be considered unreasonable for
plain updates), the amount of bloat generated by a thundering herd
could be really really bad (once per attempt per "head of
cattle"/upserter) . It's hard to say for sure how much of a problem
this is, but I think it needs to be considered. It's a problem that
I'm not sure we have the tools to analyze ahead of time. It's easier
to pin down and reason about the conventional value locking stuff,
because we know how deadlocks work. We know how to do analysis of
deadlock hazards, and the surface area actually turns out to be not
too large there.

> One fairly limitation with your current approach is that the number of
> lwlocks you can hold simultaneously is limited (MAX_SIMUL_LWLOCKS == 100).
> Another limitation is that the minimum for shared_buffers is only 16.
> Neither of those is a serious problem in real applications - no-one runs
> with shared_buffers=16 and no sane schema has a hundred unique indexes, but
> it's still something to consider.

I was under the impression, based on previously feedback, that what
I've done with LWLocks was unlikely to be accepted. I proceeded under
the assumption that we'll be able to ameliorate these problems, as for
example by implementing an alternative value locking mechanism (an
SLRU?) that is similar to what I've done to date (in particular, very
cheap and fast), but without all the down-sides that concerned Robert
and Andres, and now you. As I said, I still think that's easier and
safer than all alternative approaches described to date. It just so
happens that I also believe it will perform a lot better in the
average case too, but that isn't a key advantage to my mind.

You're right that the value locking is scary. I think we need to very
carefully consider it, once I have buy-in on the basic approach. I
really do think it's the least-worst approach described to date. It
isn't like we can't discuss making it inherently less scary, but I
hesitate to do that now, given that I don't know if that discussing
will go anywhere.

Thanks for your efforts on reviewing my work here! Do you think it
would be useful at this juncture to write a patch to make the order of
locking across unique indexes well-defined? I think it may well have
independent value to get the insertion into unique indexes (that can
throw errors) out of the way when doing a regular slot insertion.
Better to abort the transaction as soon as possible.

[1] http://www.postgresql.org/message-id/CAM3SWZRfrw+zXe7CKt6-QTCuvKQ-Oi7gnbBOPqQsvddU=9M7_g@mail.gmail.com

--
Peter Geoghegan