INSERT...ON DUPLICATE KEY LOCK FOR UPDATE

On Sun, Sep 8, 2013 at 10:21 PM, Peter Geoghegan <pg@heroku.com> wrote:

This necessitated inventing entirely new LWLock semantics around
"weakening" (from exclusive to shared) and "strengthening" (from
shared to exclusive) of locks already held. Of course, as you'd
expect, there are some tricky race hazards surrounding these new
functions that clients need to be mindful of. These have been
documented within lwlock.c.

I've since found that I can fairly reliably get this to deadlock at
high client counts (say, 95, which will do it on my 4 core laptop with
a little patience). To get this to happen, I used pgbench with a
single INSERT...ON DUPLICATE KEY IGNORE transaction script. The more
varied workload that I tested this most recent revision (v2) with the
most, with a transaction consisting on a mixture of different
statements (UPDATEs, DELETEs, INSERT...ON DUPLICATE KEY LOCK FOR
UPDATE) did not show the problem.

What I've been doing to recreate this is pgbench runs in an infinite
loop from a bash script, with a new table created for each iteration.
Each iteration has 95 clients "speculatively insert" a total of 1500
possible tuples for 15 seconds. After this period, the table has
exactly 1500 tuples, with primary key values 1 - 1500. Usually, after
about 5 - 20 minutes, deadlock occurs.

This was never a problem with the exclusive lock coding (v1),
unsurprisingly - after all, as far as buffer locks are concerned, it
did much the same thing as the existing code.

I've made some adjustments to LWLockWeaken, LWLockStrengthen and
LWLockRelease that made the deadlocks go away. Or at least, no
deadlocks or other problems manifested themselves using the same test
case for over two hours. Attached revision includes these changes, as
well as a few minor comment tweaks here and there.

I am working on an analysis of the broader deadlock hazards - the
implications of simultaneously holding multiple shared buffer locks
(that is, one for every unique index btree leaf page participating in
value locking) for the duration of a each heap tuple insertion (each
heap_insert() call). I'm particularly looking for unexpected ways in
which this locking could interact with other parts of the code that
also acquire buffer locks, for example vacuumlazy.c. I'll also try and
estimate how much of a maintainability burden unexpected locking
interactions with these other subsystems might be.

In case it isn't obvious, the deadlocking issue addressed by this
revision is not inherent to my design or anything like that - the bugs
fixed by this revision are entirely confined to lwlock.c.

--
Peter Geoghegan

Hi Peter,

Nice to see the next version, won't have time to look in any details in
the next few days tho.

On 2013-09-10 22:25:34 -0700, Peter Geoghegan wrote:

I am working on an analysis of the broader deadlock hazards - the
implications of simultaneously holding multiple shared buffer locks
(that is, one for every unique index btree leaf page participating in
value locking) for the duration of a each heap tuple insertion (each
heap_insert() call). I'm particularly looking for unexpected ways in
which this locking could interact with other parts of the code that
also acquire buffer locks, for example vacuumlazy.c. I'll also try and
estimate how much of a maintainability burden unexpected locking
interactions with these other subsystems might be.

I think for this approach to be workable you also need to explain how we
can deal with stuff like toast insertion that may need to write hundreds
of megabytes all the while leaving an entire value-range of the unique
key share locked.

I still think that even doing a plain heap insertion is longer than
acceptable to hold even a share lock over a btree page, but as long as
stuff like toast insertions happen while doing so that's peanuts.

The easiest answer is doing the toasting before doing the index locking,
but that will result in bloat, the avoidance of which seems to be the
primary advantage of your approach.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Sep 11, 2013 at 2:28 PM, Andres Freund <andres@2ndquadrant.com> wrote:

Nice to see the next version, won't have time to look in any details in
the next few days tho.

Thanks Andres!

I think for this approach to be workable you also need to explain how we
can deal with stuff like toast insertion that may need to write hundreds
of megabytes all the while leaving an entire value-range of the unique
key share locked.

Right. That is a question that needs to be addressed in a future revision.

I still think that even doing a plain heap insertion is longer than
acceptable to hold even a share lock over a btree page

Well, there is really only one way of judging something like that, and
that's to do a benchmark. I still haven't taken the time to "pick the
low hanging fruit" here that I'd mentioned - there are some fairly
obvious ways to shorten the window in which value locks are held.
Furthermore, I'm sort of at a loss as to what a fair benchmark would
look like - what is actually representative here? Also, what's the
baseline? It's not as if someone has an alternative, competing patch.
We can only hypothesize what additional costs those other approaches
introduce, unless someone has a suggestion as to how they can be
simulated without writing the full patch, which is something I'd
entertain.

As I've already pointed out, all page splits occur with the same
buffer exclusive lock held. Only, in our case, we're weakening that
lock to a shared lock. So I don't think that the heap insertion is
going to be that big of a deal, particularly in the average case.
Having said that, it's a question that surely must be closely examined
before proceeding much further. And yes, the worst case could be
pretty bad, and that surely matters too.

The easiest answer is doing the toasting before doing the index locking,
but that will result in bloat, the avoidance of which seems to be the
primary advantage of your approach.

I would say that the primary advantage of my approach is that it's
much simpler than any other approach that has been considered by
others in the past. The approach is easier to reason about because
it's really just an extension of how btrees already do value locking.
Granted, I haven't adequately demonstrated that things really are so
rosy, but I think I'll be able to. The key point is that with trivial
exception, all other parts of the code, like VACUUM, don't consider
themselves to directly have license to acquire locks on btree buffers
- they go through the AM interface instead. What do they know about
what makes sense for a particular AM? The surface area actually turns
out to be fairly manageable.

With the promise tuple approach, it's more the maintainability
overhead of new *classes* of bloat that I'm concerned about than the
bloat itself, and all the edge cases that are likely to be introduced.
But yes, the overhead of doing all that extra writing (including
WAL-logging twice), and the fact that it all has to happen with an
exclusive lock on the leaf page buffer is also a concern of mine. With
v3 of my patch, we still only have to do all the preliminary work like
finding the right page and verifying that there are no duplicates
once. So with recent revisions, the amount of time spent exclusive
locking with my proposed approach is now approximately half the time
of alternative proposals (assuming no page split is necessary). In the
worst case, the number of values locked on the leaf page is quite
localized and manageable, as a natural consequence of the fact that
it's a btree leaf page. I haven't run any numbers, but for an int4
btree (which really is the worst case here), 200 or so read-locked
values would be quite close to as bad as things got. Plus, if there
isn't a second phase of locking, which is on average a strong
possibility, those locks would be hardly held at all - contrast that
with having to do lots of exclusive locking for all that clean-up.

I might experiment with weakening the exclusive lock even earlier in
my next revision, and/or strengthening later. Off hand, I can't see a
reason for not weakening after we find the first leaf page that the
key might be on (granted, I haven't thought about it that much) -
_bt_check_unique() does not have license to alter the buffer already
proposed for insertion. Come to think of it, all of this new buffer
lock weakening/strengthening stuff might independently justify itself
as an optimization to regular btree index tuple insertion. That's a
whole other patch, though -- it's a big ambition to have as a sort of
incidental adjunct to what is already a big, complex patch.

In practice the vast majority of insertions don't involve TOASTing.
That's not an excuse for allowing the worst case to be really bad in
terms of its impact on query response time, but it may well justify
having whatever ameliorating measures we take result in bloat. It's at
least the kind of bloat we're more or less used to dealing with, and
have already invested a lot in controlling. Plus bloat-wise it can't
be any worse than just inserting the tuple and having the transaction
abort on a duplicate, since that already happens after toasting has
done its work with regular insertion.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Sep 11, 2013 at 8:47 PM, Peter Geoghegan <pg@heroku.com> wrote:

In practice the vast majority of insertions don't involve TOASTing.
That's not an excuse for allowing the worst case to be really bad in
terms of its impact on query response time, but it may well justify
having whatever ameliorating measures we take result in bloat. It's at
least the kind of bloat we're more or less used to dealing with, and
have already invested a lot in controlling. Plus bloat-wise it can't
be any worse than just inserting the tuple and having the transaction
abort on a duplicate, since that already happens after toasting has
done its work with regular insertion.

Andres is being very polite here, but the reality is that this
approach has zero chance of being accepted. You can't hold buffer
locks for a long period of time across complex operations. Full stop.
It's a violation of the rules that are clearly documented in
src/backend/storage/buffer/README, which have been in place for a very
long time, and this patch is nowhere near important enough to warrant
a revision of those rules. We are not going to risk breaking every
bit of code anywhere in the backend or in third-party code that takes
a buffer lock. You are never going to convince me, or Tom, that the
benefit of doing that is worth the risk; in fact, I have a hard time
believing that you'll find ANY committer who thinks this approach is
worth considering.

Even if you get the code to run without apparent deadlocks, that
doesn't mean there aren't any; it just means that you haven't found
them all yet. And even if you managed to squash every such hazard
that exists today, so what? Fundamentally, locking protocols that
don't include deadlock detection don't scale. You can use such locks
in limited contexts where proofs of correctness are straightforward,
but trying to stretch them beyond that point results not only in bugs,
but also in bad performance and unmaintainable code. With a much more
complex locking regimen, even if your code is absolutely bug-free,
you've put a burden on the next guy who wants to change anything; how
will he avoid breaking things? Our buffer locking regimen suffers
from painful complexity and serious maintenance difficulties as is.
Moreover, we've already got performance and scalability problems that
are attributable to every backend in the system piling up waiting on a
single lwlock, or a group of simultaneously-held lwlocks.
Dramatically broadening the scope of where lwlocks are used and for
how long they're held is going to make that a whole lot worse. What's
worse, the problems will be subtle, restricted to the people using
this feature, and very difficult to measure on production systems, and
I have no confidence they'd ever get fixed.

A further problem is that a backend which holds even one lwlock can't
be interrupted. We've had this argument before and it seems that you
don't think that non-interruptibility is a problem, but it project
policy to allow for timely interrupts in all parts of the backend and
we're not going to change that policy for this patch. Heavyweight
locks are heavy weight precisely because they provide services - like
deadlock detection, satisfactory interrupt handling, and, also
importantly, FIFO queuing behavior - that are *important* for locks
that are held over an extended period of time. We're not going to go
put those services into the lightweight lock mechanism because then it
would no longer be light weight, and we're not going to ignore the
importance of them, either.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Sep 13, 2013 at 9:23 AM, Robert Haas <robertmhaas@gmail.com> wrote:

Andres is being very polite here, but the reality is that this
approach has zero chance of being accepted.

I quite like Andres, but I have yet to see him behave as you describe
in a situation where someone proposed what was fundamentally a bad
idea. Maybe you should let him speak for himself?

You can't hold buffer
locks for a long period of time across complex operations. Full stop.
It's a violation of the rules that are clearly documented in
src/backend/storage/buffer/README, which have been in place for a very
long time, and this patch is nowhere near important enough to warrant
a revision of those rules.

The importance of this patch is a value judgement. Our users have been
screaming for this for over ten years, so to my mind it has a fairly
high importance. Also, every other database system of every stripe
worth mentioning has something approximately equivalent to this,
including ones with much less functionality generally. The fact that
we don't is a really unfortunate omission.

As to the rules you refer to, you must mean "These locks are intended
to be short-term: they should not be held for long". I don't think
that they will ever be held for long. At least, when I've managed the
amount of work that a heap_insert() can do better. I expect to produce
a revision where toasting doesn't happen with the locks held soon.
Actually, I've already written the code, I just need to do some
testing.

We are not going to risk breaking every
bit of code anywhere in the backend or in third-party code that takes
a buffer lock. You are never going to convince me, or Tom, that the
benefit of doing that is worth the risk; in fact, I have a hard time
believing that you'll find ANY committer who thinks this approach is
worth considering.

I would suggest letting those other individuals speak for themselves
too. Particularly if you're going to name someone who is on vacation
like that.

Even if you get the code to run without apparent deadlocks, that
doesn't mean there aren't any;

Of course it doesn't. Who said otherwise?

Our buffer locking regimen suffers
from painful complexity and serious maintenance difficulties as is.

That's true to a point, but it has more to do with things like how
VACUUM interacts with hio.c. Things like this:

/*
* Release the file-extension lock; it's now OK for someone else to extend
* the relation some more. Note that we cannot release this lock before
* we have buffer lock on the new page, or we risk a race condition
* against vacuumlazy.c --- see comments therein.
*/
if (needLock)
UnlockRelationForExtension(relation, ExclusiveLock);

The btree code is different, though: It implements a well-defined
interface, with much clearer separation of concerns. As I've said
already, with trivial exception (think contrib), no external code
considers itself to have license to obtain locks of any sort on btree
buffers. No external code of ours - without exception - does anything
with multiple locks, or exclusive locks on btree buffers. I'll remind
you that I'm only holding shared locks when control is outside of the
btree code.

Even within the btree code, the number of access method functions that
could conflict with what I do here (that acquire exclusive locks) is
very small when you exclude things that only exclusive lock the
meta-page (there are also very few of those). So the surface area is
quite small.

I'm not denying that there is a cost, or that I haven't expanded
things in a direction I'd prefer not to. I just think that it may well
be worth it, particularly when you consider the alternatives - this
may well be the least worst thing. I mean, if we do the promise tuple
thing, and there are multiple unique indexes, what happens when an
inserter needs to block pending the outcome of another transaction?
They had better go clean up the promise tuples from the other unique
indexes that they're trying to insert into, because they cannot afford
to hold value locks for a long time, no matter how they're
implemented. That could take much longer than just releasing a shared
buffer lock, since for each unique index the promise tuple must be
re-found from scratch. There are huge issues with additional
complexity and bloat. Oh, and now your lightweight locks aren't so
lightweight any more.

If the value locks were made interruptible through some method, such
as the promise tuples approach, does that really make deadlocking
acceptable? So at least your system didn't seize up. But on the other
hand, the user randomly had a deadlock error through no fault of their
own. The former may be worse, but the latter is also inexcusable. In
general, the best solution is just to not have deadlock hazards. I
wouldn't be surprised if reasoning about deadlocking was harder with
that alternative approach to value locking, not easier.

Moreover, we've already got performance and scalability problems that
are attributable to every backend in the system piling up waiting on a
single lwlock, or a group of simultaneously-held lwlocks.
Dramatically broadening the scope of where lwlocks are used and for
how long they're held is going to make that a whole lot worse.

You can hardly compare a buffer's LWLock with a system one that
protects critical shared memory structures. We're talking about a
shared lock on a single btree leaf page per unique index involved in
upserting.

A further problem is that a backend which holds even one lwlock can't
be interrupted. We've had this argument before and it seems that you
don't think that non-interruptibility is a problem, but it project
policy to allow for timely interrupts in all parts of the backend and
we're not going to change that policy for this patch.

I don't think non-interruptibility is a problem? Really, do you think
that this kind of inflammatory rhetoric helps anybody? I said nothing
of the sort. I recall saying something about an engineering trade-off.
Of course I value interruptibility.

If you're concerned about non-interruptibility, consider XLogFlush().
That does rather a lot of work with WALWriteLock exclusive locked. On
a busy system, some backend is very frequently going to experience a
non-interruptible wait for the duration of however long it takes to
write and flush perhaps a whole segment. All other flushing backends
are stuck in non-interruptible waits waiting for that backend to
finish. I think that the group commit stuff might have regressed
worst-case interruptibility for flushers by quite a bit; should we
have never committed that, or do you agree with my view that it's
worth it?

In contrast, what I've proposed here is in general quite unlikely to
result in any I/O for the duration of the time the locks are held.
Only writers will be blocked. And only those inserting into a narrow
range of values around the btree leaf page. Much of the work that even
those writers need to do will be unimpeded anyway; they'll just block
on attempting to acquire an exclusive lock on the first btree leaf
page that the value they're inserting could be on. And the additional
non-interruptible wait of those inserters won't be terribly much more
than the wait of the backend where heap tuple insertion takes a long
time anyway - that guy already has to do close to 100% of that work
with a non-interruptible wait today (once we eliminate
heap_prepare_insert() and toasting). The UnlockReleaseBuffer() call is
right at the end of heap_insert, and the buffer is pinned and locked
very close to the start.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

* Peter Geoghegan (pg@heroku.com) wrote:

I would suggest letting those other individuals speak for themselves
too. Particularly if you're going to name someone who is on vacation
like that.

It was my first concern regarding this patch.

Thanks,

Stephen

On Fri, Sep 13, 2013 at 12:14 PM, Stephen Frost <sfrost@snowman.net> wrote:

It was my first concern regarding this patch.

It was my first concern too.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2013-09-13 11:59:54 -0700, Peter Geoghegan wrote:

On Fri, Sep 13, 2013 at 9:23 AM, Robert Haas <robertmhaas@gmail.com> wrote:

Andres is being very polite here, but the reality is that this
approach has zero chance of being accepted.

I quite like Andres, but I have yet to see him behave as you describe
in a situation where someone proposed what was fundamentally a bad
idea. Maybe you should let him speak for himself?

Unfortunately I have to agree with Robert here, I think it's a complete
nogo to do what you propose so far and I've several times now presented
arguments why I think so.
The reason I wasn't saying "this will never get accepted" are twofold:
a) I don't want to stiffle alternative ideas to the "promises" idea,
just because I think it's the way to go. That might stop a better idea
from being articulated. b) I am not actually in the position to say it's
not going to be accepted.

*I* think that unless you make some fundamental and very, very clever
modifications to your algorithm that end up *not holding a lock over
other operations at all*, it's not going to get committed. And I'll chip
in with my -1.
And clever modification doesn't mean slightly restructuring heapam.c's
operations.

The importance of this patch is a value judgement. Our users have been
screaming for this for over ten years, so to my mind it has a fairly
high importance. Also, every other database system of every stripe
worth mentioning has something approximately equivalent to this,
including ones with much less functionality generally. The fact that
we don't is a really unfortunate omission.

I aggree it's quite important but that doesn't mean we have to do stuff
that we think are unacceptable, especially as there *are* other ways to
do it.

As to the rules you refer to, you must mean "These locks are intended
to be short-term: they should not be held for long". I don't think
that they will ever be held for long. At least, when I've managed the
amount of work that a heap_insert() can do better. I expect to produce
a revision where toasting doesn't happen with the locks held soon.
Actually, I've already written the code, I just need to do some
testing.

I personally think - and have stated so before - that doing a
heap_insert() while holding the btree lock is unacceptable.

The btree code is different, though: It implements a well-defined
interface, with much clearer separation of concerns.

Which you're completely violating by linking the btree buffer locking
with the heap locking. It's not about the btree code alone.

At this point I am a bit confused why you are asking for review.

I mean, if we do the promise tuple thing, and there are multiple
unique indexes, what happens when an inserter needs to block pending
the outcome of another transaction? They had better go clean up the
promise tuples from the other unique indexes that they're trying to
insert into, because they cannot afford to hold value locks for a long
time, no matter how they're implemented.

Why? We're using normal transaction visibility rules here. We don't stop
*other* values on the same index getting updated or similar.
And anyway. It doesn't matter which problem the "promises" idea
has. We're discussing your proposal here.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Sep 13, 2013 at 12:23 PM, Andres Freund <andres@2ndquadrant.com> wrote:

The reason I wasn't saying "this will never get accepted" are twofold:
a) I don't want to stiffle alternative ideas to the "promises" idea,
just because I think it's the way to go. That might stop a better idea
from being articulated. b) I am not actually in the position to say it's
not going to be accepted.

Well, the reality is that the promises idea hasn't been described in
remotely enough detail to compare it to what I have here. I've pointed
out plenty of problems with it. After all, it was the first thing that
I considered, and I'm on the record talking about it in the 2012 dev
meeting. I didn't take that approach for many good reasons.

The reason I ended up here is not because I didn't get the memo about
holding buffer locks across complex operations being a bad thing. At
least grant me that. I'm here because in all these years no one has
come up with a suggestion that doesn't have some very major downsides.
Like, even worse than this.

As to the rules you refer to, you must mean "These locks are intended
to be short-term: they should not be held for long". I don't think
that they will ever be held for long. At least, when I've managed the
amount of work that a heap_insert() can do better. I expect to produce
a revision where toasting doesn't happen with the locks held soon.
Actually, I've already written the code, I just need to do some
testing.

I personally think - and have stated so before - that doing a
heap_insert() while holding the btree lock is unacceptable.

Presumably your reason is essentially that we exclusive lock a heap
buffer (exactly one heap buffer) while holding shared locks on btree
index buffers. Is that really so different to holding an exclusive
lock on a btree buffer while holding a shared lock on a heap buffer?
Because that's what _bt_check_unique() does today.

Now, I'll grant you that there is one appreciable difference, which is
that multiple unique indexes may be involved. But limiting ourselves
to the primary key or something like that remains an option. And I'm
not sure that it's really any worse anyway.

The btree code is different, though: It implements a well-defined
interface, with much clearer separation of concerns.

Which you're completely violating by linking the btree buffer locking
with the heap locking. It's not about the btree code alone.

You're right that it isn't about just the btree code.

In order for a deadlock to occur, there must be a mutual dependency.
What code could feel entitled to hold buffer locks on btree buffers
and heap buffers at the same time except the btree code itself? It
already does so. But no one else does the same thing. If anyone did
anything with a heap buffer lock held that could result in a call into
one of the btree access method functions (I'm not contemplating the
possibility of this other code locking the btree buffer *directly*),
I'm quite sure that that would be rejected outright today, because
that causes deadlocks. Certainly, vacuumlazy.c doesn't do it, for
example. Why would anyone ever want to do that anyway? I cannot think
of any reason. I suppose that that does still leave "transitive
dependencies", but now you're stretching things. After all, you're not
supposed to hold buffer locks for long! The dependency would have to
transit through, say, one of the system LWLocks used for WAL Logging.
Seems pretty close to impossible that it'd be an issue - index stuff
is only WAL-logged as index tuples are inserted (that is, as the locks
are finally released). Everyone automatically does that kind of thing
in a consistent order of locking, unlocking in the opposite order
anyway.

But what of the btree code deadlocking with itself? There are only a
few functions (2 or 3) where that's possible even in principle. I
think that they're going to be not too hard to analyze. For example,
with insertion, the trick is to always lock in a consistent order and
unlock/insert in the opposite order. The heap shared lock(s) needed in
the btree code cannot deadlock with another upserter because once the
other upserter has that exclusive heap buffer lock, it's *inevitable*
that it will release all of its shared buffer locks. Granted, I could
stand to think about this case more, but you get the idea - it *is*
possible to clamp down on the code that needs to care about this stuff
to a large degree. It's subtle, but btrees are generally considered
pretty complicated, and the btree code already cares about some odd
cases like these (it takes special precuations for catalog indexes,
for example).

The really weird thing about my patch is that the btree code trusts
the executor to call the heapam code to do the right thing in the
right way - it now knows more than I'd prefer. Would you be happier if
the btree code took more direct responsibility for the heap tuple
insertion instead? Before you say "that's ridiculous", consider the
big modularity violation that has always existed. It may be no more
ridiculous than that. And that existing state of affairs may be no
less ridiculous than living with what I've already done.

At this point I am a bit confused why you are asking for review.

I am asking for us, collectively, through consensus, to resolve the
basic approach to doing this. That was something I stated right up
front, pointing out details of where the discussion had gone in the
past. That was my explicit goal. There has been plenty of discussing
on this down through the years, but nothing ever came from it.

Why is this an intractable problem for over a decade for us alone? Why
isn't this a problem for other database systems? I'm not implying that
it's because they do this. It's something that I am earnestly
interested in, though. A number of people have asked me that, and I
don't have a good answer for them.

I mean, if we do the promise tuple thing, and there are multiple
unique indexes, what happens when an inserter needs to block pending
the outcome of another transaction? They had better go clean up the
promise tuples from the other unique indexes that they're trying to
insert into, because they cannot afford to hold value locks for a long
time, no matter how they're implemented.

Why? We're using normal transaction visibility rules here. We don't stop
*other* values on the same index getting updated or similar.

Because you're locking a value in some other, earlier unique index,
all the while waiting *indefinitely* on some other value in a second
or subsequent one. That isn't acceptable. A bunch of backends would
back up just because one backend had this contention on the second
unique index value that the others didn't actually have themselves. My
design allows those other backends to immediately go through and
finish.

Value locks have these kinds of hazards no matter how you implement
them. Deadlocks, and unreasonable stalling as described here is always
unacceptable - whether or not the problems are detected at runtime is
ultimately of marginal interest. Either way, it's a bug.

I think that the details of how this approach compare to others are
totally pertinent. For me, that's the whole point - getting towards
something that will balance all of these concerns and be acceptable.
Yes, it's entirely possible that that could look quite different to
what I have here. I do not want to reduce all this to a question of
"is this one design acceptable or not?". Am I not allowed to propose a
design to drive discussion? That's how the most important features get
implemented around here.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Peter Geoghegan <pg@heroku.com> wrote:

we exclusive lock a heap buffer (exactly one heap buffer) while
holding shared locks on btree index buffers. Is that really so
different to holding an exclusive lock on a btree buffer while
holding a shared lock on a heap buffer? Because that's what
_bt_check_unique() does today.

Is it possible to get a deadlock doing only one of those two
things?  Is it possible to avoid a deadlock doing both of them?

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Sep 13, 2013 at 2:59 PM, Peter Geoghegan <pg@heroku.com> wrote:

I would suggest letting those other individuals speak for themselves
too. Particularly if you're going to name someone who is on vacation
like that.

You seem to be under the impression that I'm mentioning Tom's name, or
Andres's, because I need to win some kind of an argument. I don't.
We're not going to accept a patch that uses lwlocks in the way that
you are proposing.

I mean, if we do the promise tuple
thing, and there are multiple unique indexes, what happens when an
inserter needs to block pending the outcome of another transaction?
They had better go clean up the promise tuples from the other unique
indexes that they're trying to insert into, because they cannot afford
to hold value locks for a long time, no matter how they're
implemented.

As Andres already pointed out, this is not correct. Just to add to
what he said, we already have long-lasting value locks in the form of
SIREAD locks. SIREAD can exist at different levels of granularity, but
one of those levels is index-page-level granularity, where they have
the function of guarding against concurrent insertions of values that
would fall within that page, which just so happens to be the same
thing you want to do here. The difference between those locks and
what you're proposing here is that they are implemented differently.
That is why those were acceptable and this is not.

That could take much longer than just releasing a shared
buffer lock, since for each unique index the promise tuple must be
re-found from scratch. There are huge issues with additional
complexity and bloat. Oh, and now your lightweight locks aren't so
lightweight any more.

Yep, totally agreed. If you simply lock the buffer, or take some
other action which freezes out all concurrent modifications to the
page, then re-finding the lock is much simpler. On the other hand,
it's much simpler precisely because you've reduced concurrency to the
degree necessary to make it simple. And reducing concurrency is bad.
Similarly, complexity and bloat are not great things taken in
isolation, but many of our existing locking schemes are already very
complex. Tuple locks result in a complex jig that involves locking
the tuple via the heavyweight lock manager, performing a WAL-logged
modification to the page, and then releasing the lock in the
heavyweight lock manager. As here, that is way more expensive than
simply grabbing and holding a share-lock on the page. But we get a
number of important benefits out of it. The backend remains
interruptible while the tuple is locked, the protocol for granting
locks is FIFO to prevent starvation, we don't suppress page eviction
while the lock is held, we can simultaneously lock arbitrarily large
numbers of tuples, and deadlocks are detect and handled cleanly. If
those requirements were negotiable, we would surely have negotiated
them away already, because the performance benefits would be immense.

If the value locks were made interruptible through some method, such
as the promise tuples approach, does that really make deadlocking
acceptable?

Yes. It's not possible to prevent all deadlocks. It IS possible to
make sure that they are properly detected and that precisely one of
the transactions involved is rolled back to resolve the deadlock.

You can hardly compare a buffer's LWLock with a system one that
protects critical shared memory structures. We're talking about a
shared lock on a single btree leaf page per unique index involved in
upserting.

Actually, I can and I am. Buffers ARE critical shared memory structures.

A further problem is that a backend which holds even one lwlock can't
be interrupted. We've had this argument before and it seems that you
don't think that non-interruptibility is a problem, but it project
policy to allow for timely interrupts in all parts of the backend and
we're not going to change that policy for this patch.

I don't think non-interruptibility is a problem? Really, do you think
that this kind of inflammatory rhetoric helps anybody? I said nothing
of the sort. I recall saying something about an engineering trade-off.
Of course I value interruptibility.

I don't see what's inflammatory about that statement. The point is
that this isn't the first time you've proposed a change which would
harm interruptibility and it isn't the first time I've objected on
precisely that basis. Interruptibility is not a nice-to-have that we
can trade away from time to time; it's essential and non-negotiable.

If you're concerned about non-interruptibility, consider XLogFlush().
That does rather a lot of work with WALWriteLock exclusive locked. On
a busy system, some backend is very frequently going to experience a
non-interruptible wait for the duration of however long it takes to
write and flush perhaps a whole segment. All other flushing backends
are stuck in non-interruptible waits waiting for that backend to
finish. I think that the group commit stuff might have regressed
worst-case interruptibility for flushers by quite a bit; should we
have never committed that, or do you agree with my view that it's
worth it?

It wouldn't take a lot to convince me that it wasn't worth it, because
I was never all that excited about that patch to begin with. I think
it mostly helps in extremely artificial situations that are not likely
to occur on real systems anyway. But, yeah, WALWriteLock is a
problem, no doubt about it. We should try to make the number of such
problems go down, not up, even if it means passing up new features
that we'd really like to have.

In contrast, what I've proposed here is in general quite unlikely to
result in any I/O for the duration of the time the locks are held.
Only writers will be blocked. And only those inserting into a narrow
range of values around the btree leaf page. Much of the work that even
those writers need to do will be unimpeded anyway; they'll just block
on attempting to acquire an exclusive lock on the first btree leaf
page that the value they're inserting could be on.

Sure, but you're talking about broadening the problem from the guy
performing the insert to everybody who might be trying to an insert
that hits one of the same unique-index pages. Instead of holding one
buffer lock, the guy performing the insert is now holding as many
buffer locks as there are indexes. That's a non-trivial issue.

For that matter, if the table has more than MAX_SIMUL_LWLOCKS indexes,
you'll error out. In fact, if you get the number of indexes exactly
right, you'll exceed MAX_SIMUL_LWLOCKS in visibilitymap_clear() and
panic the whole system.

Oh, and if different backends load the index list in different orders,
because say the system catalog gets vacuumed between their respective
relcache loads, then they may try to lock the indexes in different
orders and cause an undetected deadlock.

And, drifting a bit further off-topic, even to get as far as you have,
you've added overhead to every lwlock acquisition and release, even
for people who never use this functionality. I'm pretty skeptical
about anything that involves adding additional frammishes to the
lwlock mechanism. There are a few new primitives I'd like, too, but
every one we add slows things down for everybody.

And the additional
non-interruptible wait of those inserters won't be terribly much more
than the wait of the backend where heap tuple insertion takes a long
time anyway - that guy already has to do close to 100% of that work
with a non-interruptible wait today (once we eliminate
heap_prepare_insert() and toasting). The UnlockReleaseBuffer() call is
right at the end of heap_insert, and the buffer is pinned and locked
very close to the start.

That's true but somewhat misleading. Textually most of the function
holds the buffer lock, but heap_prepare_insert(),
CheckForSerializableConflictIn(), and RelationGetBufferForTuple(), and
XLogWrite() are the parts that do substantial amounts of computation,
and only the last of those happens while holding the buffer lock. And
that last is really fundamental, because we can't let any other
backend see the modified buffer until we've xlog'd the changes. The
problems you're proposing to create do not fall into the same
category.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

I haven't read the patch and the btree code is an area I really don't know,
so take this for what it's worth....

It seems to me that the nature of the problem is that there will
unavoidably be a nexus between the two parts of the code here. We can try
to isolate it as much as possible but we're going to need a bit of a
compromise.

I'm imagining a function that takes two target heap buffers and a btree
key. It would descend the btree and holding the leaf page lock do a
try_lock on the heap pages. If it fails to get the locks then it releases
whatever it got and returns for the heap update to find new pages and try
again.

This still leaves the potential problem with page splits and I assume it
would still be tricky to call it without unsatisfactorily mixing executor
and btree code. But that's as far as I got.

--
greg

On 2013-09-14 09:57:43 +0100, Greg Stark wrote:

It seems to me that the nature of the problem is that there will
unavoidably be a nexus between the two parts of the code here. We can try
to isolate it as much as possible but we're going to need a bit of a
compromise.

I think Roberts and mine point is that there are several ways to
approach this without doing that.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2013-09-13 14:41:46 -0700, Peter Geoghegan wrote:

On Fri, Sep 13, 2013 at 12:23 PM, Andres Freund <andres@2ndquadrant.com> wrote:

The reason I wasn't saying "this will never get accepted" are twofold:
a) I don't want to stiffle alternative ideas to the "promises" idea,
just because I think it's the way to go. That might stop a better idea
from being articulated. b) I am not actually in the position to say it's
not going to be accepted.

Well, the reality is that the promises idea hasn't been described in
remotely enough detail to compare it to what I have here. I've pointed
out plenty of problems with it.

Even if you disagree, I still think that doesn't matter in the very
least. You say:

I think that the details of how this approach compare to others are
totally pertinent. For me, that's the whole point - getting towards
something that will balance all of these concerns and be acceptable.

Well, the two other people involved in the discussion so far have gone
on the record saying that the presented approach is not acceptable to
them. And you haven't started reacting to that.

Yes, it's entirely possible that that could look quite different to
what I have here. I do not want to reduce all this to a question of
"is this one design acceptable or not?".

But the way you're discussing it so far is exactly reducing it that way.

If you want the discussion to be about *how* can we implement it that
the various concerns are addressed: fsck*ing great. I am with you there.

In the end, even though I have my usual strong opinions which is the
best way, I don't care which algorithm gets pursued further. At least,
if, and only if, it has a fighting chance of getting committed. Which
this doesn't.

After all, it was the first thing that
I considered, and I'm on the record talking about it in the 2012 dev
meeting. I didn't take that approach for many good reasons.

Well, I wasn't there when you said that ;)

The reason I ended up here is not because I didn't get the memo about
holding buffer locks across complex operations being a bad thing. At
least grant me that. I'm here because in all these years no one has
come up with a suggestion that doesn't have some very major downsides.
Like, even worse than this.

I think you're massively, massively, massively overstating the dangers
of bloat here. It's a known problem that's *NOT* getting worse by any of
the other proposals if you compare it with the loop/lock/catch
implementation of upsert that we have today as the only option. And we
*DO* have infrastructure to deal with bloat, even if could use some
improvement. We *don't* have infrastructure with deadlocks on
lwlocks. And we're not goint to get that infrastructure, because it
would even further remove the "lw" part of lwlocks.

As to the rules you refer to, you must mean "These locks are intended
to be short-term: they should not be held for long". I don't think
that they will ever be held for long. At least, when I've managed the
amount of work that a heap_insert() can do better. I expect to produce
a revision where toasting doesn't happen with the locks held soon.
Actually, I've already written the code, I just need to do some
testing.

I personally think - and have stated so before - that doing a
heap_insert() while holding the btree lock is unacceptable.

Presumably your reason is essentially that we exclusive lock a heap
buffer (exactly one heap buffer) while holding shared locks on btree
index buffers.

It's that it interleaves an already complex but local locking scheme
that required several years to become correct with another that is just
the same. That's an utterly horrid idea.

Is that really so different to holding an exclusive
lock on a btree buffer while holding a shared lock on a heap buffer?
Because that's what _bt_check_unique() does today.

Yes, it it is different. But, in my opinion, bt_check_unique() doing so
is a bug that needs fixing. Not something that we want to extend.

(Note that _bt_check_unique() already needs to deal with the fact that
it reads an unlocked page, because it moves right in some cases)

And, as you say:

Now, I'll grant you that there is one appreciable difference, which is
that multiple unique indexes may be involved. But limiting ourselves
to the primary key or something like that remains an option. And I'm
not sure that it's really any worse anyway.

I don't think that's an acceptable limitation. If it were something we
could lift in a release or two, maybe, but that's not what you're
talking about.

At this point I am a bit confused why you are asking for review.

I am asking for us, collectively, through consensus, to resolve the
basic approach to doing this. That was something I stated right up
front, pointing out details of where the discussion had gone in the
past. That was my explicit goal. There has been plenty of discussing
on this down through the years, but nothing ever came from it.

At the moment ISTM you're not conceding on *ANY* points. That's not very
often the way to find concensus.

Why is this an intractable problem for over a decade for us alone? Why
isn't this a problem for other database systems? I'm not implying that
it's because they do this. It's something that I am earnestly
interested in, though. A number of people have asked me that, and I
don't have a good answer for them.

Afaik all those go the route of bloat, don't they? Also, at least in the
past, mysql had a long list of caveats around it...

I mean, if we do the promise tuple thing, and there are multiple
unique indexes, what happens when an inserter needs to block pending
the outcome of another transaction? They had better go clean up the
promise tuples from the other unique indexes that they're trying to
insert into, because they cannot afford to hold value locks for a long
time, no matter how they're implemented.

Why? We're using normal transaction visibility rules here. We don't stop
*other* values on the same index getting updated or similar.

Because you're locking a value in some other, earlier unique index,
all the while waiting *indefinitely* on some other value in a second
or subsequent one. That isn't acceptable. A bunch of backends would
back up just because one backend had this contention on the second
unique index value that the others didn't actually have themselves. My
design allows those other backends to immediately go through and
finish.

That argument doesn't make sense to me. You're inserting a unique
value. It completely makes sense that you can only insert one of
them. If it's unclear whether you can insert, you're going to have to
wait. Thats why they are UNIQUE after all. You're describing a complete
nonadvantange here. It's also how unique indexes already work.
Also note, that wait's on xids are properly supervised by deadlock detection.

Even if it had an advantage, not blocking *for the single unique key alone*
opens you to issues of livelocks where several backends retry because of
each other indefinitely.

Value locks have these kinds of hazards no matter how you implement
them. Deadlocks, and unreasonable stalling as described here is always
unacceptable - whether or not the problems are detected at runtime is
ultimately of marginal interest. Either way, it's a bug.

Whether postgres locks down in a way that can only resolved by kill -9
or whether it aborts a transaction are, like, a couple of magnitude of a
difference.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Sat, Sep 14, 2013 at 12:22 AM, Robert Haas <robertmhaas@gmail.com> wrote:

I mean, if we do the promise tuple
thing, and there are multiple unique indexes, what happens when an
inserter needs to block pending the outcome of another transaction?
They had better go clean up the promise tuples from the other unique
indexes that they're trying to insert into, because they cannot afford
to hold value locks for a long time, no matter how they're
implemented.

As Andres already pointed out, this is not correct.

While not doing this is not incorrect, it certainly would be useful
for preventing deadlocks and unnecessary contention. In a world where
people expect either an insert or an update, we ought to try and
reduce contention across multiple unique indexes. I can understand why
that doesn't matter today, though - if you're going to insert
duplicates indifferent to whether or not there will be conflicts,
that's a kind of abuse, and not worth optimizing - seems probable that
most transactions will commit. However, it seems much less probable
that most upserters will insert. People may well wish to upsert all
the time where an insert is hardly ever necessary, which is one reason
why I have doubts about other proposals.

Note that today there is no guarantee that the original waiter for a
duplicate-inserting xact to complete will be the first one to get a
second chance, so I think it's hard to question this on correctness
grounds. Even if they are released in FIFO order, there is no reason
to assume that the first waiter will win the race with a second. Most
obviously, the second waiter may not even ever get the chance to block
on the same xid at all (so it's not really a waiter at all) and still
be able to insert, if the blocking-xact aborts after the second
"waiter" starts its descent but before it checks uniqueness. All this,
even though the second "waiter" arrived maybe minutes after the first.

What I'm talking about here is really unlikely to result in lock
starvation, because the original waiter typically gets to observe the
other waiter go through, and that's reason enough to give up entirely.
Now, it's kind of weird that the original waiter will still end up
blocking on the xid that caused it to wait in the first instance. So
there should be more thought put into that, like remembering the xid
and only waiting on it on a retry, or some similar scheme. Maybe you
could contrive a scenario where this causes lock starvation, but I
suspect you could do the same thing for the present btree insertion
code.

Just to add to
what he said, we already have long-lasting value locks in the form of
SIREAD locks. SIREAD can exist at different levels of granularity, but
one of those levels is index-page-level granularity, where they have
the function of guarding against concurrent insertions of values that
would fall within that page, which just so happens to be the same
thing you want to do here. The difference between those locks and
what you're proposing here is that they are implemented differently.
That is why those were acceptable and this is not.

As the implementer of this patch, I'm obligated to put some checks in
unique index insertion that everyone has to care about. There is no
way around that. Complexity issues aside, I think that an argument
could be made for this approach *reducing* the impact on concurrency
relative to other approaches, if there isn't too many unique indexes
to deal with, which is the case the vast majority of the time. I mean,
those other approaches necessitate doing so much more with *exclusive*
locks held. Like inserting, maybe doing a page split, WAL-logging, all
with the lock, and then either updating in place or killing the
promise tuple, and WAL-logging that, with an exclusive lock held the
second time around. Plus searching for everything twice. I think that
frequently killing all of those broken-promise tuples could have
deleterious effects on concurrency and/or index bloat or the kind only
remedied by reindex. Do you update the freespace map too? More
exclusive locks! Or if you leave it up to VACUUM (and just set the xid
to InvalidXid, which is still extra work), autovacuum has to care
about a new *class* of bloat - index-only bloat. Plus lots of dead
duplicates are bad for performance in btrees generally.

As here, that is way more expensive than
simply grabbing and holding a share-lock on the page. But we get a
number of important benefits out of it. The backend remains
interruptible while the tuple is locked, the protocol for granting
locks is FIFO to prevent starvation, we don't suppress page eviction
while the lock is held, we can simultaneously lock arbitrarily large
numbers of tuples, and deadlocks are detect and handled cleanly. If
those requirements were negotiable, we would surely have negotiated
them away already, because the performance benefits would be immense.

False equivalence. We only need to lock as many unique index *values*
(not tuples) as are proposed for insertion per slot (which can be
reasonably bound), and only for an instant. Clearly it would be
totally unacceptable if tuple-level locks made backends
uninterruptible indefinitely. Of course, this is nothing like that.

If the value locks were made interruptible through some method, such
as the promise tuples approach, does that really make deadlocking
acceptable?

Yes. It's not possible to prevent all deadlocks. It IS possible to
make sure that they are properly detected and that precisely one of
the transactions involved is rolled back to resolve the deadlock.

You seem to have misunderstood me here, or perhaps I was unclear. I'm
referring to deadlocks that cannot really be predicted or analyzed by
the user at all - see my comments below on insertion order.

I don't think non-interruptibility is a problem? Really, do you think
that this kind of inflammatory rhetoric helps anybody? I said nothing
of the sort. I recall saying something about an engineering trade-off.
Of course I value interruptibility.

I don't see what's inflammatory about that statement.

The fact that you simply stated that I don't think
non-interruptibility is a problem in a non-qualified way, obviously.

Interruptibility is not a nice-to-have that we
can trade away from time to time; it's essential and non-negotiable.

I seem to recall you saying something about the Linux kernel and their
attitude to interruptibility. Yes, interruptibility is not just a
nice-to-have; it is essentially. However, without dismissing your
other concerns, I have yet to hear a convincing argument as to why
anything I've done here is going to make any difference to
interruptibility that would be appreciable to any human. So far it's
been a slippery slope type argument that can be equally well used to
argue against some facet of almost any substantial patch ever
proposed. I just don't think that regressing interruptibility
marginally is *necessarily* sufficient justification for rejecting an
approach outright. FYI, *that's* how I value interruptibility
generally.

In contrast, what I've proposed here is in general quite unlikely to
result in any I/O for the duration of the time the locks are held.
Only writers will be blocked. And only those inserting into a narrow
range of values around the btree leaf page. Much of the work that evehn
those writers need to do will be unimpeded anyway; they'll just block
on attempting to acquire an exclusive lock on the first btree leaf
page that the value they're inserting could be on.

Sure, but you're talking about broadening the problem from the guy
performing the insert to everybody who might be trying to an insert
that hits one of the same unique-index pages.

In general, that isn't that much worse than just blocking the value
directly. The number of possible values that could also be blocked is
quite low. The chances of it actually mattering that those additional
values are locked in the still small window in which the buffer locks
are held is in generally fairly low, particularly on larger tables
where there is naturally a large number of possible distinct values. I
will however concede that the impact on inserters that want to insert
a non-locked value that belongs on the locked page or its child might
be worse, but it's already a problem that inserted index tuples can
all end up on the same page, if not to the same extent.

Instead of holding one
buffer lock, the guy performing the insert is now holding as many
buffer locks as there are indexes. That's a non-trivial issue.

Actually, as many buffer locks as there are *unique* indexes. It might
be a non-trivial issue, but this whole problem is decidedly
non-trivial, as I'm sure we can all agree.

For that matter, if the table has more than MAX_SIMUL_LWLOCKS indexes,
you'll error out. In fact, if you get the number of indexes exactly
right, you'll exceed MAX_SIMUL_LWLOCKS in visibilitymap_clear() and
panic the whole system.

Oh, come on. We can obviously engineer a solution to that problem. I
don't think I've ever seen a table with close to 100 *unique* indexes.
4 or 5 is a very high number. If we just raised on error if someone
tried to do this with more than 10 unique indexes, I would guess
that'd we'd get exactly zero complaints about it.

Oh, and if different backends load the index list in different orders,
because say the system catalog gets vacuumed between their respective
relcache loads, then they may try to lock the indexes in different
orders and cause an undetected deadlock.

Undetected deadlock is really not much worse than detected deadlock
here. Either way, it's a bug. And it's something that any kind of
implementation will need to account for. It's not okay to
*unpredictably* deadlock, in a way that the user has no control over.
Today, someone can do an analysis of their application and eliminate
deadlocks if they need to. That might not be terribly practical much
of the time, but it can be done. It certainly is practical to do it in
a localized way. I wouldn't like to compromise that.

So yes, you're right that I need to control for this sort of thing
better than in the extant patch, and in fact this was discussed fairly
early on. But it's an inherent problem.

And, drifting a bit further off-topic, even to get as far as you have,
you've added overhead to every lwlock acquisition and release, even
for people who never use this functionality.

If you look at the code, you'll see that I've made very modest
modifications to LWLockRelease only. I would be extremely surprised if
the overhead was not only in the noise, but was completely impossible
to detect through any conventional benchmark. These are the same kind
of very modest changes made for LWLockAcquireOrWait(), and you said
nothing about that at the time. Despite the fact that you now appear
to think that that whole effort was largely a waste of time.

That's true but somewhat misleading. Textually most of the function
holds the buffer lock, but heap_prepare_insert(),
CheckForSerializableConflictIn(), and RelationGetBufferForTuple(), and
XLogWrite() are the parts that do substantial amounts of computation,
and only the last of those happens while holding the buffer lock.

I've already written modifications so that I don't have to do
heap_prepare_insert() with the locks held. There is no reason to call
CheckForSerializableConflictIn() with the additional locks held
either. After all, "For a heap insert, we only need to check for
table-level SSI locks". As for RelationGetBufferForTuple(), yes, the
majority of the time it will have to do very little without acquiring
an exclusive lock, because it's going to get that from the last place
a heap tuple was inserted from.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Sat, Sep 14, 2013 at 3:15 PM, Andres Freund <andres@2ndquadrant.com> wrote:

Well, the reality is that the promises idea hasn't been described in
remotely enough detail to compare it to what I have here. I've pointed
out plenty of problems with it.

Even if you disagree, I still think that doesn't matter in the very
least.

It matters if you care about getting this feature.

You say:

I think that the details of how this approach compare to others are
totally pertinent. For me, that's the whole point - getting towards
something that will balance all of these concerns and be acceptable.

Well, the two other people involved in the discussion so far have gone
on the record saying that the presented approach is not acceptable to
them. And you haven't started reacting to that.

Uh, yes I have. I'm not really sure what you could mean by that. What
am I refusing to address?

Yes, it's entirely possible that that could look quite different to
what I have here. I do not want to reduce all this to a question of
"is this one design acceptable or not?".

But the way you're discussing it so far is exactly reducing it that way.

The fact that I was motivated to do things this way serves to
illustrate the problems generally.

If you want the discussion to be about *how* can we implement it that
the various concerns are addressed: fsck*ing great. I am with you there.

Isn't that what we were doing? There has been plenty of commentary on
alternative approaches.

In the end, even though I have my usual strong opinions which is the
best way, I don't care which algorithm gets pursued further. At least,
if, and only if, it has a fighting chance of getting committed. Which
this doesn't.

I don't think that any design that has been described to date doesn't
have serious problems. Causing excessive bloat, particularly in
indexes is a serious problem also.

The reason I ended up here is not because I didn't get the memo about
holding buffer locks across complex operations being a bad thing. At
least grant me that. I'm here because in all these years no one has
come up with a suggestion that doesn't have some very major downsides.
Like, even worse than this.

I think you're massively, massively, massively overstating the dangers
of bloat here. It's a known problem that's *NOT* getting worse by any of
the other proposals if you compare it with the loop/lock/catch
implementation of upsert that we have today as the only option.

Why would I compare it with that? That's terrible, and very few of our
users actually know about it anyway. Also, will an UPDATE followed by
an INSERT really bloat all that much anyway?

And we
*DO* have infrastructure to deal with bloat, even if could use some
improvement. We *don't* have infrastructure with deadlocks on
lwlocks. And we're not goint to get that infrastructure, because it
would even further remove the "lw" part of lwlocks.

Everything I said so far is predicated on LWLocks not deadlocking
here, so I'm not really sure why you'd say that. If I can't find a way
to prevent deadlock, then clearly the approach is doomed.

It's that it interleaves an already complex but local locking scheme
that required several years to become correct with another that is just
the same. That's an utterly horrid idea.

You're missing my point, which is that it may be possible, with
relatively modest effort, to analyze things to ensure that deadlock is
impossible - regardless of the complexities of the two systems -
because they're reasonably well encapsulated. See below, under "I'll
say it again".

Now, I can certainly understand why you wouldn't be willing to accept
that at face value. The idea isn't absurd, though. You could think of
the heap_insert() call as being under the control of the btree code
(just as, say, heap_hot_search() is), even though the code isn't at
all structured that way, and that's awkward. I'm actually slightly
tempted to structure it that way.

Is that really so different to holding an exclusive
lock on a btree buffer while holding a shared lock on a heap buffer?
Because that's what _bt_check_unique() does today.

Yes, it it is different. But, in my opinion, bt_check_unique() doing so
is a bug that needs fixing. Not something that we want to extend.

Well, I think you know that that's never going to happen. There are
all kinds of reasons why it works that way that cannot be disavowed.
My definition of a bug includes a user being affected.

At this point I am a bit confused why you are asking for review.

I am asking for us, collectively, through consensus, to resolve the
basic approach to doing this. That was something I stated right up
front, pointing out details of where the discussion had gone in the
past. That was my explicit goal. There has been plenty of discussing
on this down through the years, but nothing ever came from it.

At the moment ISTM you're not conceding on *ANY* points. That's not very
often the way to find concensus.

Really? I've conceded plenty of points. Just now I conceded a point to
Robert about insertion being blocked for inserters that want to insert
a value that isn't already locked/existing, and he didn't even raise
that in the first place. Most prominently, I've conceded that it is
entirely questionable that I hold the buffer locks for longer - before
you even responded to my original patch! I've said it many many times
many many ways. It should be heavily scrutinized. But you both seem to
be making general points along those lines, without reference to what
I've actually done. Those general points could almost to the same
extent apply to _bt_check_unique() today, which is why I have a hard
time accepting them at face value. To say that what that function does
is "a bug" is just not credible, because it's been around in
essentially the same form since at least a time when you and I were in
primary school. I'll remind you that you haven't been able to
demonstrate deadlock in a way that invalidates my approach. While of
course that's not how this is supposed to work, I've been too busy
defending myself here to get down to the business of carefully
analysing the relatively modest interactions between btree and heap
that could conceivably introduce a deadlock. Yes, the burden to prove
this can't deadlock is mine, but I thought I'd provide you with the
opportunity to prove that it can.

I'll say it again: For a deadlock, there needs to be a mutual
dependency. Provided the locking phase doesn't acquire any locks other
than buffer locks, and during the interaction with the heap btree
inserters (or the locking phase) cannot acquire heap locks in a way
that conflicts with other upserters, we will be fine. It doesn't
necessarily matter how complex each system individually is, because
the two meet in such a limited area (well, two areas now, I suppose),
and they only meet in one direction - there is no reciprocation where
the heap code locks or otherwise interacts with index buffers. When
the heap insertion is performed, all index value locks are already
acquired. The locking phase cannot block itself because of the
ordering of locking, but also because the locks on the heap that it
takes are only shared locks.

Now, this analysis is somewhat complex, and underdeveloped. But as
Robert said, there are plenty of things about locking in Postgres that
are complex and subtle. He also said that it doesn't matter if I can
prove that it won't deadlock, but I'd like a second opinion on that,
since my proof might actually be, if not simple, short, and therefore
may not represent an ongoing burden in the way Robert seemed to think
it would.

That argument doesn't make sense to me. You're inserting a unique
value. It completely makes sense that you can only insert one of
them.

Even if it had an advantage, not blocking *for the single unique key alone*
opens you to issues of livelocks where several backends retry because of
each other indefinitely.

See my remarks to Robert.

Whether postgres locks down in a way that can only resolved by kill -9
or whether it aborts a transaction are, like, a couple of magnitude of a
difference.

Not really. I can see the advantage of having the deadlock be
detectable from a defensive-coding standpoint. But index locking
ordering inconsistencies, and the deadlocks they may cause are not
acceptable generally.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Sat, Sep 14, 2013 at 1:57 AM, Greg Stark <stark@mit.edu> wrote:

It seems to me that the nature of the problem is that there will unavoidably
be a nexus between the two parts of the code here. We can try to isolate it
as much as possible but we're going to need a bit of a compromise.

Exactly. That's why all the proposals with the exception of this one
have to date involved unacceptable bloating - that's how they try and
span the nexus.

I'll find it very difficult to accept any implementation that is going
to bloat things even worse than our upsert looping example. The only
advantage of such an implementation over the upsert example is that
it'll avoid burning through subxacts. The main reason I don't want to
take that approach is that I know it won't be accepted, because it's a
disaster. That's why the people that proposed this in various forms
down through the years haven't gone and implemented it themselves. I
do not accept that all of this is like the general situation with row
locks. I do not think that the big costs of having many dead
duplicates in a unique index can be overlooked (or perhaps the cost of
cleaning them up eagerly, which is something I'd also expect to work
very badly). That's something that's going to reverberate all over the
place. Imagine a simple, innocent looking pattern that resulted in
there being unique indexes that became hugely bloated. It's not hard.

What I will concede (what I have conceded, actually) is that it would
be better if the locks were more granular. Now, I'm not so much
concerned about concurrent inserters inserting values that just so
happen to be values that were locked. It's more the case that I'm
worried about inserters blocking on other values that are incidentally
locked despite not already existing, that would go on the locked page
or maybe a later page. In particular, I'm concerned about the impact
on SERIAL primary key columns. Not exactly an uncommon case (though
one I'd already thought to optimize by locking last).

What I think might actually work acceptably is if we were to create an
SLRU that kept track of value-locks per buffer. The challenge there
would be to have regular unique index inserters care about them, while
having little to no impact on their regular performance. This might be
possible by having them check the buffer for external value locks in
the SLRU immediately after exclusive locking the buffer - usually that
only has to happen once per index tuple insertion (assuming no
duplicates necessitate retry). If they find their value in the SLRU,
they do something like unlock and block on the other xact and restart.
Now, obviously a lot of the details would have to be worked out, but
it seems possible.

In order for any of this to really be possible, there'd have to be
some concession made to my position, as Greg mentions here. In other
words, I'd need buy-in for the general idea of holding locks in shared
memory from indexes across heap tuple insertion (subject to a sound
deadlock analysis, of course). Some modest compromises may need to be
made around interruptibility. I'd also probably need agreement that
it's okay that value locks can not last more than an instant (they
cannot be held indefinitely pending the end of a transaction). This
isn't something that I imagine to be too controversial, because it's
true today for a single unique index. As I've already outlined, anyone
waiting on another transaction with a would-be duplicate to commit has
very few guarantees about the order that it'll get its second shot
relative to the order it initial queued up behind the successful but
not-yet-committed inserter.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 15 Sep 2013 10:19, "Peter Geoghegan" <pg@heroku.com> wrote:

On Sat, Sep 14, 2013 at 1:57 AM, Greg Stark <stark@mit.edu> wrote:

It seems to me that the nature of the problem is that there will

unavoidably

be a nexus between the two parts of the code here. We can try to

isolate it

as much as possible but we're going to need a bit of a compromise.

In order for any of this to really be possible, there'd have to be
some concession made to my position, as Greg mentions here. In other
words, I'd need buy-in for the general idea of holding locks in shared
memory from indexes across heap tuple insertion (subject to a sound
deadlock analysis, of course).

Actually that wasn't what I meant by that.

What I meant is that there going to be some code coupling between the
executor and btree code. That's purely a question of course structure, and
will be true regardless of the algorithm you settle on.

What I was suggesting was an api for a function that would encapsulate that
coupling. The executor would call this function which would promise to
obtain all the locks needed for both operations or give up. Effectively it
would be a special btree operation which would have special knowledge of
the executor only in that it knows that being able to get a lock on two
heap buffers is something the executor needs sometimes.

I'm not sure this fits well with your syntax since it assumes the update
will happen at the same time as the index lookup but as I said I haven't
read your patch, maybe it's not incompatible. I'm writing all this on my
phone so it's mostly just pie in the sky brainstorming. I'm sorry if it's
entirely irrelevant.

Peter Geoghegan <pg@heroku.com> wrote:

There is no reason to call CheckForSerializableConflictIn() with
the additional locks held either. After all, "For a heap insert,
we only need to check for table-level SSI locks".

You're only talking about not covering that call with a *new*
LWLock, right?  We put some effort into making sure that such calls
were only inside of LWLocks which were needed for correctness.

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2013-09-15 02:19:41 -0700, Peter Geoghegan wrote:

On Sat, Sep 14, 2013 at 1:57 AM, Greg Stark <stark@mit.edu> wrote:

It seems to me that the nature of the problem is that there will unavoidably
be a nexus between the two parts of the code here. We can try to isolate it
as much as possible but we're going to need a bit of a compromise.

Exactly. That's why all the proposals with the exception of this one
have to date involved unacceptable bloating - that's how they try and
span the nexus.

I'll find it very difficult to accept any implementation that is going
to bloat things even worse than our upsert looping example.

How would any even halfway sensible example cause *more* bloat than the
upsert looping thing?
I'll concede that bloat is something to be aware of, but just because
it's *an* issue, it's not *the* only issue.

In all the solutions I can think of/have heard of that have the chance
of producing additional bloat also have good chance of cleaning up the
additional bloat.

In the "promises" approach you simply can mark the promise index tuples
as LP_DEAD in the IGNORE case if you've found a conflicting tuple. In
the OR UPDATE case you can immediately reuse them. There's no heap
bloat. The logic for dead items already exists in nbtree, so that's not
too much complication. The case where that doesn't work is when postgres
dies inbetween or we're signalled to abort. But that produces bloat for
normal DML anyway. Any vacuum or insert can check whether the promise
xid has committed and remove the promise otherwise.

In the proposals that involve just inserting the heaptuple and then
handle the uniqueness violation when inserting the index tuples you can
immediately mark the index tuples as dead and mark it as prunable.

The only advantage of such an implementation over the upsert example is that
it'll avoid burning through subxacts. The main reason I don't want to
take that approach is that I know it won't be accepted, because it's a
disaster. That's why the people that proposed this in various forms
down through the years haven't gone and implemented it themselves. I
do not accept that all of this is like the general situation with row
locks.

The primary advantage will be that it's actually usable by users without
massive overhead in writing dozens of functions.

I don't think the bloat issue had much to do with the feature not
getting implemented so far. It's that nobody was willing to do the work
and endure the discussions around it. And I definitely applaud you for
finally tackling the issue despite that.

I do not think that the big costs of having many dead
duplicates in a unique index can be overlooked

Why would there be so many duplicate index tuples? The primary user of
this is going to be UPSERT. In case there's a conflicting tuple, there
is going to be a new tuple version. Which will need a new index entry
quite often. If there's no conflict, we will insert anyway.
So, there's the case of UPSERTs that could be done as HOT updates
because there's enough space on the page and none of the indexes
actually have changed. As explained above, we can simply mark the index
tuple as dead in that case (don't even need an exclusive lock for that,
if done right).

(or perhaps the cost of
cleaning them up eagerly, which is something I'd also expect to work
very badly).

Why? Remember the page you did the insert to, do a _bt_moveright() to
catch eventual splits. Mark the item as dead. Done. The next insert will
repack the page if necessary (cf. _bt_findinsertloc).

What I will concede (what I have conceded, actually) is that it would
be better if the locks were more granular. Now, I'm not so much
concerned about concurrent inserters inserting values that just so
happen to be values that were locked. It's more the case that I'm
worried about inserters blocking on other values that are incidentally
locked despite not already existing, that would go on the locked page
or maybe a later page. In particular, I'm concerned about the impact
on SERIAL primary key columns. Not exactly an uncommon case (though
one I'd already thought to optimize by locking last).

Yes, I think that's the primary issue from a scalability and performance
POV. Locking entire ranges of values, potentially even on inner pages
(because you otherwise would have to split) isn't going to work.

What I think might actually work acceptably is if we were to create an
SLRU that kept track of value-locks per buffer. The challenge there
would be to have regular unique index inserters care about them, while
having little to no impact on their regular performance. This might be
possible by having them check the buffer for external value locks in
the SLRU immediately after exclusive locking the buffer - usually that
only has to happen once per index tuple insertion (assuming no
duplicates necessitate retry). If they find their value in the SLRU,
they do something like unlock and block on the other xact and restart.
Now, obviously a lot of the details would have to be worked out, but
it seems possible.

If you can make that work, without locking heap and btree pages at the
same time, yes, I think that's a possible way forward. One way to offset
the cost of SLRU in the common case where there is no contention would
be to have a page level flag that triggers that lookup. There should be
space in btpo_flags.

In order for any of this to really be possible, there'd have to be
some concession made to my position, as Greg mentions here. In other
words, I'd need buy-in for the general idea of holding locks in shared
memory from indexes across heap tuple insertion (subject to a sound
deadlock analysis, of course).

I don't have a fundamental problem with holding locks during the
insert. I have a problem with holding page level lightweight locks on
the btree and the heap at the same time.

Some modest compromises may need to be made around interruptibility.

Why? As far as I understand that proposal, I don't see why that would be needed?

I'd also probably need agreement that
it's okay that value locks can not last more than an instant (they
cannot be held indefinitely pending the end of a transaction). This
isn't something that I imagine to be too controversial, because it's
true today for a single unique index. As I've already outlined, anyone
waiting on another transaction with a would-be duplicate to commit has
very few guarantees about the order that it'll get its second shot
relative to the order it initial queued up behind the successful but
not-yet-committed inserter.

I forsee problems here.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Sat, Sep 14, 2013 at 6:27 PM, Peter Geoghegan <pg@heroku.com> wrote:

Note that today there is no guarantee that the original waiter for a
duplicate-inserting xact to complete will be the first one to get a
second chance, so I think it's hard to question this on correctness
grounds. Even if they are released in FIFO order, there is no reason
to assume that the first waiter will win the race with a second. Most
obviously, the second waiter may not even ever get the chance to block
on the same xid at all (so it's not really a waiter at all) and still
be able to insert, if the blocking-xact aborts after the second
"waiter" starts its descent but before it checks uniqueness. All this,
even though the second "waiter" arrived maybe minutes after the first.

ProcLockWakeup() only wakes as many waiters from the head of the queue
as can all be granted the lock without any conflicts. So I don't
think there is a race condition in that path.

So far it's
been a slippery slope type argument that can be equally well used to
argue against some facet of almost any substantial patch ever
proposed.

I don't completely agree with that characterization, but you do have a
point. Obviously, if the differences in the area of interruptibility,
starvation, deadlock risk, etc. can be made small enough relative to
the status quo can be made small enough, then those aren't reasons to
reject the approach.

But I'm skeptical that you're going to be able to accomplish that,
especially without adversely affecting maintainability. I think the
way that you're proposing to use lwlocks here is sufficiently
different from what the rest of the system does that it's going to be
hard to avoid system-wide affects that can't easily be caught during
code review; and like Andres, I don't share your skepticism about
alternative approaches.

For that matter, if the table has more than MAX_SIMUL_LWLOCKS indexes,
you'll error out. In fact, if you get the number of indexes exactly
right, you'll exceed MAX_SIMUL_LWLOCKS in visibilitymap_clear() and
panic the whole system.

Oh, come on. We can obviously engineer a solution to that problem. I
don't think I've ever seen a table with close to 100 *unique* indexes.
4 or 5 is a very high number. If we just raised on error if someone
tried to do this with more than 10 unique indexes, I would guess
that'd we'd get exactly zero complaints about it.

That's not a solution; that's a hack.

Undetected deadlock is really not much worse than detected deadlock
here. Either way, it's a bug. And it's something that any kind of
implementation will need to account for. It's not okay to
*unpredictably* deadlock, in a way that the user has no control over.
Today, someone can do an analysis of their application and eliminate
deadlocks if they need to. That might not be terribly practical much
of the time, but it can be done. It certainly is practical to do it in
a localized way. I wouldn't like to compromise that.

I agree that unpredictable deadlocks are bad. I think the fundamental
problem with UPSERT, MERGE, and this proposal is what happens when the
conflicting tuple is present but not visible to your scan, either
because it hasn't committed yet or because it has committed but is not
visible to your snapshot. I'm not clear on how you handle that in
your approach.

If you look at the code, you'll see that I've made very modest
modifications to LWLockRelease only. I would be extremely surprised if
the overhead was not only in the noise, but was completely impossible
to detect through any conventional benchmark. These are the same kind
of very modest changes made for LWLockAcquireOrWait(), and you said
nothing about that at the time. Despite the fact that you now appear
to think that that whole effort was largely a waste of time.

Well, I did have some concerns about the performance impact of that patch:

/messages/by-id/CA+TgmoaPyQKEaoFz8HkDGvRDbOmRpkGo69zjODB5=7Jh3hbPQA@mail.gmail.com

I also discovered, after it was committed, that it didn't help in the
way I expected:

/messages/by-id/CA+TgmoY8P3sD=oUViG+xZjmZk5-phuNV39rtfyzUQxU8hJtZxw@mail.gmail.com

It's true that I didn't raise those concerns contemporaneously with
the commit, but I didn't understand the situation well enough at that
time to realize how narrow the benefit was.

I've wished, on a number of occasions, to be able to add more lwlock
primitives. The problem with that is that if everybody does it, we'll
pretty soon end up with a mess. I attempted to address that with this
proposal:

/messages/by-id/CA+Tgmob4YE_k5dpO0T07PNf1SOKPybo+wj4m4FryOS7Z4_yOzg@mail.gmail.com

...but nobody (including me) was very sure that was the right way
forward, and it never went anywhere. However, I think the basic issue
remains. I was sad to discover last week that Heikki handled this
problem for the WAL scalability patch by basically copy-and-pasting
much of the lwlock code and then hacking it up. I think we're well on
our way to an unmaintainable mess already, and I don't want it to get
worse. :-(

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2013-09-17 12:29:51 -0400, Robert Haas wrote:

But I'm skeptical that you're going to be able to accomplish that,
especially without adversely affecting maintainability. I think the
way that you're proposing to use lwlocks here is sufficiently
different from what the rest of the system does that it's going to be
hard to avoid system-wide affects that can't easily be caught during
code review;

I actually think extending lwlocks to allow downgrading an exclusive
lock is a good idea, independent of this path, and I think there are
some areas of the code where we could use that capability to increase
scalability. Now, that might be because I pretty much suggested using
them in such a way to solve some of the problems :P

I don't think they solve the issue of this patch (holding several nbtree
pages locked across heap operations) though.

I agree that unpredictable deadlocks are bad. I think the fundamental
problem with UPSERT, MERGE, and this proposal is what happens when the
conflicting tuple is present but not visible to your scan, either
because it hasn't committed yet or because it has committed but is not
visible to your snapshot. I'm not clear on how you handle that in
your approach.

Hm. I think it should be handled exactly the way we handle it for unique
indexes today. Wait till it's clear whether you can proceed.
At some point we might to extend that logic to more cases, but that
should be separate discussion imo.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Sep 17, 2013 at 6:20 PM, Andres Freund <andres@2ndquadrant.com> wrote:

I agree that unpredictable deadlocks are bad. I think the fundamental
problem with UPSERT, MERGE, and this proposal is what happens when the
conflicting tuple is present but not visible to your scan, either
because it hasn't committed yet or because it has committed but is not
visible to your snapshot. I'm not clear on how you handle that in
your approach.

Hm. I think it should be handled exactly the way we handle it for unique
indexes today. Wait till it's clear whether you can proceed.

That's what I do, although getting those details right has been of
secondary concern for obvious reasons.

At some point we might to extend that logic to more cases, but that
should be separate discussion imo.

This is essentially why I went and added a row locking component over
your objections. Value locks (regardless of implementation)
effectively stop an insertion from finishing, but not from starting.
ISTM that locking the row with value locks held can cause deadlock.
So, unfortunately, we cannot really discuss value locking and row
locking separately, even though I see the appeal of trying to. Gaining
an actual representative notion of the expense of releasing and
re-acquiring the locks is too tightly coupled with how this is handled
and how frequently we need to restart. Plus there may well be other
issues in the same vein that we've yet to consider.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2013-09-18 00:54:38 -0500, Peter Geoghegan wrote:

At some point we might to extend that logic to more cases, but that
should be separate discussion imo.

This is essentially why I went and added a row locking component over
your objections.

I didn't object to implementing row level locking. I said that if your
basic algorithm without row level locks is viewn as being broken, it
won't be fixed by implementing row level locking.

What I meant here is just that we shouldn't implement a mode with less
waiting for now even if there might be usecases because that will open
another can of worms.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Sep 17, 2013 at 9:29 AM, Robert Haas <robertmhaas@gmail.com> wrote:

On Sat, Sep 14, 2013 at 6:27 PM, Peter Geoghegan <pg@heroku.com> wrote:

Note that today there is no guarantee that the original waiter for a
duplicate-inserting xact to complete will be the first one to get a
second chance

ProcLockWakeup() only wakes as many waiters from the head of the queue
as can all be granted the lock without any conflicts. So I don't
think there is a race condition in that path.

Right, but what about XactLockTableWait() itself? It only acquires a
ShareLock on the xid of the got-there-first inserter that potentially
hasn't yet committed/aborted. There will be no conflicts between
multiple second-chance-seeking blockers trying to acquire this lock
concurrently, and so in fact there is (what I guess you'd consider to
be) a race condition in the current btree insertion code. So my
earlier point about according an upsert implementation license to
optimize ordering of retries across multiple unique indexes -- that it
isn't really inconsistent with the current code when dealing with only
one unique index insertion -- has not been invalidated.

EvalPlanQualFetch() and Do_MultiXactIdWait() also call
XactLockTableWait(), for similar reasons. In my patch, the later row
locking code used by INSERT...ON DUPLICATE KEY LOCK FOR UPDATE calls
XactLockTableWait() too.

So far it's
been a slippery slope type argument that can be equally well used to
argue against some facet of almost any substantial patch ever
proposed.

I don't completely agree with that characterization, but you do have a
point. Obviously, if the differences in the area of interruptibility,
starvation, deadlock risk, etc. can be made small enough relative to
the status quo can be made small enough, then those aren't reasons to
reject the approach.

That all seems fair to me. That's the standard that I'd apply as a
reviewer myself.

But I'm skeptical that you're going to be able to accomplish that,
especially without adversely affecting maintainability. I think the
way that you're proposing to use lwlocks here is sufficiently
different from what the rest of the system does that it's going to be
hard to avoid system-wide affects that can't easily be caught during
code review;

Fair enough. In case it isn't already totally clear to someone, I
concede that it isn't going to be workable to hold even shared buffer
locks across all these operations. Let's get past that, though.

and like Andres, I don't share your skepticism about
alternative approaches.

Well, I expressed skepticism about one alternative approach in
particular, which is the promise tuples approach. Andres seems to
think that I'm overly concerned about bloat, but I'm not sure he
appreciates why I'm so sensitive to it in this instance. I'll be
particularly sensitive to it if value locks need to be held
indefinitely rather than there being a speculative
grab-the-value-locks attempt (because that increases the window in
which another session can necessitate that we retry at row locking
time quite considerably - see below).

I think the fundamental
problem with UPSERT, MERGE, and this proposal is what happens when the
conflicting tuple is present but not visible to your scan, either
because it hasn't committed yet or because it has committed but is not
visible to your snapshot.

Yeah, you're right. As I mentioned to Andres already, when row locking
happens and there is this kind of conflict, my approach is to retry
from scratch (go right back to before value lock acquisition) in the
sort of scenario that generally necessitates EvalPlanQual() looping,
or to throw a serialization failure where that's appropriate. After an
unsuccessful attempt at row locking there could well be an interim
wait for another xact to finish, before retrying (at read committed
isolation level). This is why I think that value locking/retrying
should be cheap, and should avoid bloat if at all possible.

Forgive me if I'm making a leap here, but it seems like what you're
saying is that the semantics of upsert that one might naturally expect
are *arguably* fundamentally impossible, because they entail
potentially locking a row that isn't current to your snapshot, and you
cannot throw a serialization failure at read committed. I respectfully
suggest that that exact definition of upsert isn't a useful one,
because other snapshot isolation/MVCC systems operating within the
same constraints must have the same issues, and yet they manage to
implement something that could be called upsert that people seem happy
with.

I also discovered, after it was committed, that it didn't help in the
way I expected:

/messages/by-id/CA+TgmoY8P3sD=oUViG+xZjmZk5-phuNV39rtfyzUQxU8hJtZxw@mail.gmail.com

Well, at the time you didn't also provide raw commit latency benchmark
results for your hardware using a tool like pg_test_fsync, which I'd
consider absolutely essential to such a discussion. That's mostly or
entirely what the group commit stuff does - amortize that cost among
concurrently flushing transactions. Around this time, the patch was
said by Heikki to just relieve lock contention around WALWriteLock -
the 9.2 release notes say much the same. I never understood it that
way, though Heikki disagreed with that [1]/messages/by-id/4FB0A673.7040002@enterprisedb.com.

Certainly, if relieving contention was all the patch did, then you
wouldn't expect the 9.3 commit_delay implementation to help anyone,
but it does: with a slow fsync holding the lock 50% *longer* can
actually help tremendously. So I *always* agreed with you that there
was hardware where group commit would barely help with a moderately
sympathetic benchmark like the pgbench default. Not that it matters
much now.

It's true that I didn't raise those concerns contemporaneously with
the commit, but I didn't understand the situation well enough at that
time to realize how narrow the benefit was.

I've wished, on a number of occasions, to be able to add more lwlock
primitives. The problem with that is that if everybody does it, we'll
pretty soon end up with a mess.

I wouldn't go that far. The number of possible additional primitives
that are useful isn't that high, unless we decide that LWLocks are
going to be a fundamentally different thing, which I consider
unlikely.

/messages/by-id/CA+Tgmob4YE_k5dpO0T07PNf1SOKPybo+wj4m4FryOS7Z4_yOzg@mail.gmail.com

...but nobody (including me) was very sure that was the right way
forward, and it never went anywhere. However, I think the basic issue
remains. I was sad to discover last week that Heikki handled this
problem for the WAL scalability patch by basically copy-and-pasting
much of the lwlock code and then hacking it up. I think we're well on
our way to an unmaintainable mess already, and I don't want it to get
worse. :-(

I hear what you're saying about LWLocks. I did follow the FlexLocks
stuff at the time myself. Obviously we aren't going to add new lwlock
operations if they have exactly no clients. However, I think that the
semantics implemented (weakening and strengthening of locks) may well
be handy somewhere else. So while I wouldn't go and commit that stuff
on the off chance that it will be useful, it's worth bearing in mind
going forward that it's quite possible to weaken/strengthen locks.

[1]: /messages/by-id/4FB0A673.7040002@enterprisedb.com

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Peter,

* Peter Geoghegan (pg@heroku.com) wrote:

Forgive me if I'm making a leap here, but it seems like what you're
saying is that the semantics of upsert that one might naturally expect
are *arguably* fundamentally impossible, because they entail
potentially locking a row that isn't current to your snapshot, and you
cannot throw a serialization failure at read committed. I respectfully
suggest that that exact definition of upsert isn't a useful one,

I'm not sure I follow this completely- you're saying that a definition
of 'upsert' which includes having to lock rows which aren't in your
current snapshot (for reasons stated) isn't a useful one. Is the
implication that a useful definition of 'upsert' is that it *doesn't*
have to lock rows which aren't in your current snapshot, and if so, then
what would the semantics of that upsert look like?

because other snapshot isolation/MVCC systems operating within the
same constraints must have the same issues, and yet they manage to
implement something that could be called upsert that people seem happy
with.

This I am generally in agreement with, to the extent that 'upsert' is
something we really want and we should figure out a way to get there
from here, but it wouldn't be the first time that we worked out a
better solution than existing implementations. So, another '+1' from me
wrt your working this issue and please don't get too discouraged that
there's a lot of pressure to find a magic bullet- I think part of it is
exactly because everyone wants this and wants it to be better than
what's out there today.

Thanks,

Stephen

Hi Stephen,

On Fri, Sep 20, 2013 at 6:55 PM, Stephen Frost <sfrost@snowman.net> wrote:

I'm not sure I follow this completely- you're saying that a definition
of 'upsert' which includes having to lock rows which aren't in your
current snapshot (for reasons stated) isn't a useful one. Is the
implication that a useful definition of 'upsert' is that it *doesn't*
have to lock rows which aren't in your current snapshot, and if so, then
what would the semantics of that upsert look like?

No, I'm suggesting that the useful semantics are that it does
potentially lock rows not yet visible to our snapshot that have
committed - the latest row version. I see no alternative (we can't
throw a serialization failure at read committed isolation level), and
Andres seemed to agree that this was the way forward. Robert described
problems he saw with this a few years ago [1]/messages/by-id/AANLkTineR-rDFWENeddLg=GrkT+epMHk2j9X0YqpiTY8@mail.gmail.com -- Peter Geoghegan. It *is* a problem (we
need to think very carefully about it), but, as I've said, it is a
problem that anyone implementing this feature for a Snapshot
Isolation/MVCC database would have to deal with, and several have.

So, what the patch does right now is (if you squint) analogous to how
SELECT FOR UPDATE uses EvalPlanQual already. However, instead of
re-verifying a qual, we're re-verifying that the value locking has
identified the right tid (there will probably be a different one in
the subsequent iteration, or maybe we *can* go insert this time). We
need consensus across unique indexes to go ahead with insertion, but
once we know that we can't (and have a tid to lock), value locks can
go away - we'll know if anything has changed about the tid's logical
row that we need to care about when row locking. Besides, holding
value locks while row locking has deadlock hazards, and, because value
locks only stop insertions *finishing*, holding on to them is at best
pointless.

The tid we get from locking, that points to a would-be duplicate heap
tuple has always committed - otherwise we'd never return from locking,
because that blocks pending the outcome of a duplicate-inserting-xact
(and only returns the tid when that xact commits). Even though this
tuple is known to be visible, it may be deleted in the interim before
row locking, in which case restarting from before value locking is
appropriate. It might also be updated, which would necessitate locking
a later row version in order to prevent race conditions. But it seems
dangerous, invasive, and maybe even generally impossible to try and
wait for the transaction that updated to commit or abort so that we
can lock that later version the usual way (the usual EvalPlanQual
looping thing) - better to restart value locking.

The fundamental observation about value locking (at least for any
half-way reasonable implementation), that I'd like to emphasize, is
that short of a radical overhaul that would have many downsides, it
can only ever prevent insertion from *finishing*. The big picture of
my design is that it tries to quickly grab value locks, release them
and grab a row lock (or insert heap tuples, index tuples, and then
release value locks). If row locking fails, it waits for the
conflicter xact to finish, and then restarts before the value locking
of the current slot. If you think that's kind of questionable, maybe
you have a point, but consider:

1. How else are you going to handle it if row locking needs to handle
conflicts? You might say "I can re-verify that no unique index columns
were affected instead", and maybe you can, but what if that doesn't
help because they *were* changed? Besides, doesn't this break the
amcanunique contract? Surely judging what's really a duplicate is the
AM's job.

You're back to "I need to throw an error to get out of this but I have
no good excuse to do so at read committed" -- you've lost the usual
duplicate key error "excuse". I don't think you can expect holding the
value locks throughout row locking to help, because, as I've said,
that causes morally indefensible deadlocks, and besides, it doesn't
stop what row locking would consider to be a conflict, it just stops
insertion from *finishing*.

2. In the existing btree index insertion code, the order that retries
occur in the event of unique index tuple insertion finding an
unfinished conflicting xact *is* undefined. Yes, that's right - the
first waiter is not guaranteed to be the first to get a second chance.
It's not even particularly probable! See remarks from my last mail to
Robert for more information.

3. People with a real purist's view on the (re)ordering of value
locking must already think that EvalPlanQual() is completely ghetto
for very similar reasons, and as such should just go use a higher
isolation level. For the rest of us, what concurrency control anomaly
can allowing this cause over and above what's already possible there?
Are lock starvation risks actually appreciably raised at all?

What Andres and Robert seem to expect generally - that value locks
only be released when we the locker has a definitive answer - actually
*can* be ensured at the higher isolation levels, where the system has
license to bail out by throwing a serialization failure. The trick
there is just to throw an error if the first *retry* at cross-index
value locking is unsuccessful or blocks on a whole other xact -- a
serialization error (and not a unique constraint violation error, as
would often but not necessarily otherwise occur for non-upserters).
Naturally, it could also happen that at > read committed, row locking
throws a serialization failure (as is always mandated over using
EvalPlanQual() or other monkeying around at higher isolation levels).

This I am generally in agreement with, to the extent that 'upsert' is
something we really want and we should figure out a way to get there
from here, but it wouldn't be the first time that we worked out a
better solution than existing implementations. So, another '+1' from me
wrt your working this issue and please don't get too discouraged that
there's a lot of pressure to find a magic bullet

Thanks for the encouragement!

[1]: /messages/by-id/AANLkTineR-rDFWENeddLg=GrkT+epMHk2j9X0YqpiTY8@mail.gmail.com -- Peter Geoghegan
--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Sun, Sep 15, 2013 at 8:23 AM, Andres Freund <andres@2ndquadrant.com> wrote:

I'll find it very difficult to accept any implementation that is going
to bloat things even worse than our upsert looping example.

How would any even halfway sensible example cause *more* bloat than the
upsert looping thing?

I was away in Chicago over the week, and didn't get to answer this.
Sorry about that.

In the average/uncontended case, the subxact example bloats less than
all alternatives to my design proposed to date (including the "unborn
heap tuple" idea Robert mentioned in passing to me in person the other
day, which I think is somewhat similar to a suggestion of Heikki's
[1]: /messages/by-id/45E845C4.6030000@enterprisedb.com
contention usually doesn't happen. But you need to also appreciate
that because of the way row locking works and the guarantees value
locking makes, any ON DUPLICATE KEY LOCK FOR UPDATE implementation is
going to have to potentially restart in more places (as compared to
the doc's example), maybe including value locking of each unique index
and certainly including row locking. So the contended case might even
be worse as well.

On average, it is quite likely that either the UPDATE or INSERT will
succeed - there has to be some concurrent activity around the same
values for either to fail, and in general that's quite unlikely. If
the UPDATE doesn't succeed, it won't bloat, and it's then very likely
that the INSERT at the end of the loop will go ahead and succeed
without itself creating bloat.

Going forward with this discussion, I would like us all to take as
read that the buffer locking stuff is a prototype approach to value
locking, to be refined later (subject to my basic design being judged
fundamentally sound). I don't think anyone believes that it's
fundamentally incorrect in that it doesn't do something that it claims
to do (concerns are more around what it might do or prevent that it
shouldn't), and it can still drive discussion in a very useful
direction. So far criticism of this patch has almost entirely been on
aspects of buffer locking, but it would be much more useful for the
time being to simply assume that the buffer locks *are* interruptible.
It's probably okay with me to still be a bit suspicious of
deadlocking, though, because if we refine the buffer locking using a
more granular SLRU value locking approach, that doesn't necessarily
guarantee that it's impossible, even if it does (I guess) prevent
undesirable interactions with other buffer locking.

[1]: /messages/by-id/45E845C4.6030000@enterprisedb.com

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Sep 20, 2013 at 5:48 PM, Peter Geoghegan <pg@heroku.com> wrote:

ProcLockWakeup() only wakes as many waiters from the head of the queue
as can all be granted the lock without any conflicts. So I don't
think there is a race condition in that path.

Right, but what about XactLockTableWait() itself? It only acquires a
ShareLock on the xid of the got-there-first inserter that potentially
hasn't yet committed/aborted. There will be no conflicts between
multiple second-chance-seeking blockers trying to acquire this lock
concurrently, and so in fact there is (what I guess you'd consider to
be) a race condition in the current btree insertion code.

I should add: README.tuplock says the following:

"""

The protocol for waiting for a tuple-level lock is really

LockTuple()
XactLockTableWait()
mark tuple as locked by me
UnlockTuple()

When there are multiple waiters, arbitration of who is to get the lock next
is provided by LockTuple().

"""

So because this isn't a tuple-level lock - it's really a value-level
lock - LockTuple() is not called by the btree code at all, and so
arbitration of who gets the lock is, as I've said, essentially
undefined.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Sat, Sep 21, 2013 at 7:22 PM, Peter Geoghegan <pg@heroku.com> wrote:

So because this isn't a tuple-level lock - it's really a value-level
lock - LockTuple() is not called by the btree code at all, and so
arbitration of who gets the lock is, as I've said, essentially
undefined.

Addendum: It isn't even a value-level lock, because the buffer locks
are of course released before the XactLockTableWait() call. It's a
simple attempt to acquire a shared lock on an xid.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Hi,

I don't have time to answer the other emails today (elections,
climbing), but maybe you could clarify the below?

On 2013-09-21 17:07:11 -0700, Peter Geoghegan wrote:

On Sun, Sep 15, 2013 at 8:23 AM, Andres Freund <andres@2ndquadrant.com> wrote:

I'll find it very difficult to accept any implementation that is going
to bloat things even worse than our upsert looping example.

How would any even halfway sensible example cause *more* bloat than the
upsert looping thing?

I was away in Chicago over the week, and didn't get to answer this.
Sorry about that.

In the average/uncontended case, the subxact example bloats less than
all alternatives to my design proposed to date (including the "unborn
heap tuple" idea Robert mentioned in passing to me in person the other
day, which I think is somewhat similar to a suggestion of Heikki's
[1]). The average case is very important, because in general
contention usually doesn't happen.

I can't follow here. Why does e.g. the promise tuple approach bloat more
than the subxact example?
The protocol is roughly:
1) Insert index pointer containing an xid to be waiting upon instead of
the target tid into all indexes
2) Insert heap tuple, we can be sure there's no conflict now
3) Go through the indexes and repoint the item to point to the tid of the
heaptuple instead of the xid.

There's zero heap or index bloat in the uncontended case. In the
contended case it's just the promise tuples from 1) that are inserted
before the conflict is detected. Those can be marked as dead when the
conflict happened.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Sun, Sep 22, 2013 at 2:10 AM, Andres Freund <andres@2ndquadrant.com> wrote:

I can't follow here. Why does e.g. the promise tuple approach bloat more
than the subxact example?
The protocol is roughly:
1) Insert index pointer containing an xid to be waiting upon instead of
the target tid into all indexes
2) Insert heap tuple, we can be sure there's no conflict now
3) Go through the indexes and repoint the item to point to the tid of the
heaptuple instead of the xid.

There's zero heap or index bloat in the uncontended case. In the
contended case it's just the promise tuples from 1) that are inserted
before the conflict is detected. Those can be marked as dead when the
conflict happened.

It depends on your definition of the contended case. You're assuming
that insertion is the most probable outcome, when in fact much of the
time updating is just as likely or even more likely. Many promise
tuples may be inserted before actually seeing a conflict and deciding
to update/lock for update. In order for the example in the docs to
bloat at all, both the UPDATE and the INSERT need to fail within a
tiny temporal window - that's what I mean by uncontended (it is
usually tiny because if the UPDATE blocks, that often means it will
succeed anyway, but if not the INSERT will very probably succeed).

This is because the UPDATE won't bloat when no existing row is seen,
because its subplan will return no rows. The INSERT will only bloat if
it fails, which is generally very unlikely because of the fact that
the UPDATE just did nothing. Contrast that with bloating almost every
time an UPDATE is necessary (I think that bloat that is generally
cleaned up synchronously is still bloat). That's before we even talk
about the additional overhead. Making the locks expensive to
release/clean-up could really hurt, since it appears they'll *have* to
be unlocked before row locking, and during that time concurrent
activity affecting the row to be locked can necessitate a full restart
- that's a window we want to keep as small as possible.

I think reviewer time would for now be much better spent discussing
the patch at a higher level (along the lines of my recent mail to
Stephen and Robert). I've been at least as guilty as anyone else in
getting mired in these details. We'll be much better equipped to have
this discussion afterwards, because it isn't clear to us if we really
need or would find it at all useful to have long-lasting value locks,
how frequently we'll need to retry and for what reasons, and so on.

My immediate concern as the patch author is to come up with a better
answer to the problem that Robert described [1]/messages/by-id/AANLkTineR-rDFWENeddLg=GrkT+epMHk2j9X0YqpiTY8@mail.gmail.com, because "hey, I
locked the row -- you take it from here user that might not have any
version of it visible to you" is not good enough. I hope that there
isn't a tension between solving that problem and offering the
flexibility and composability of the proposed syntax.

[1]: /messages/by-id/AANLkTineR-rDFWENeddLg=GrkT+epMHk2j9X0YqpiTY8@mail.gmail.com

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2013-09-22 12:54:57 -0700, Peter Geoghegan wrote:

On Sun, Sep 22, 2013 at 2:10 AM, Andres Freund <andres@2ndquadrant.com> wrote:

I can't follow here. Why does e.g. the promise tuple approach bloat more
than the subxact example?
The protocol is roughly:
1) Insert index pointer containing an xid to be waiting upon instead of
the target tid into all indexes
2) Insert heap tuple, we can be sure there's no conflict now
3) Go through the indexes and repoint the item to point to the tid of the
heaptuple instead of the xid.

There's zero heap or index bloat in the uncontended case. In the
contended case it's just the promise tuples from 1) that are inserted
before the conflict is detected. Those can be marked as dead when the
conflict happened.

It depends on your definition of the contended case. You're assuming
that insertion is the most probable outcome, when in fact much of the
time updating is just as likely or even more likely. Many promise
tuples may be inserted before actually seeing a conflict and deciding
to update/lock for update.

I still fail to see how that's relevant. For every index there's two
things that can happen:
a) there's a conflicting tuple. In that case we can fail at that
point/convert to an update. No Bloat.
b) there's no conflicting tuple. In that case we will insert a promise
tuple. If there's no conflict in further indexes (i.e. we INSERT), the
promise will converted to a plain tuple. If there *is* a further
conflict, you *still* need the new index tuple because by definition
(the index changed) it cannot be an HOT update. So you convert it as
well. No Bloat.

I think that bloat that is generally cleaned up synchronously is still
bloat

I don't think it's particularly relevant because the above will just
cause bloat in case of rollbacks and such which is nothin new, but:
I fail to fee the point of such a position.

I think reviewer time would for now be much better spent discussing
the patch at a higher level (along the lines of my recent mail to
Stephen and Robert).

Yes, I plan to reply to those, I just didn't have time to do so this
weekend. There's other stuff than PG every now and then ;)

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Sun, Sep 22, 2013 at 1:39 PM, Andres Freund <andres@2ndquadrant.com> wrote:

I still fail to see how that's relevant. For every index there's two
things that can happen:
a) there's a conflicting tuple. In that case we can fail at that
point/convert to an update. No Bloat.

Well, yes - if the conflict is in the first unique index you look at.

b) there's no conflicting tuple. In that case we will insert a promise
tuple.

Yeah, if there is no conflict relating to any of the tuples, the cost
is limited to updating the promise tuples in-place. Not exactly a
trivial additional cost even then though, because you have to
exclusive lock and WAL-log twice per index tuple.

If there's no conflict in further indexes (i.e. we INSERT), the
promise will converted to a plain tuple.

Sure.

If there *is* a further
conflict, you *still* need the new index tuple because by definition
(the index changed) it cannot be an HOT update.

By definition? What do you mean? This isn't MySQL's REPLACE. This
feature is almost certainly going to tacitly require the user to write
the upsert SQL with a particular unique index in mind (to figure that
out for ourselves, we'd need to somehow ask/infer, which is ugly/very
hard to impossible). The UPDATE, as typically written, probably
*won't* actually update any of the other, incidentally
unique-constrained/value locked columns that we have to check in case
that's what the user really meant, and very probably not the
"interesting" column appearing in the UPDATE qual itself, so it
probably *will* be a HOT update.

So you convert it as
well. No Bloat.

Even if this is a practical possibility, which I doubt, the book
keeping sounds very messy and invasive indeed.

Yes, I plan to reply to those, I just didn't have time to do so this
weekend.

Great, thanks. I cannot strongly emphasize enough how I think that's
the way to frame all of this. So much so that I almost managed to
resist answering the above points. :-)

There's other stuff than PG every now and then ;)

Hope you enjoyed the hike.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Sep 20, 2013 at 8:48 PM, Peter Geoghegan <pg@heroku.com> wrote:

On Tue, Sep 17, 2013 at 9:29 AM, Robert Haas <robertmhaas@gmail.com> wrote:

On Sat, Sep 14, 2013 at 6:27 PM, Peter Geoghegan <pg@heroku.com> wrote:

Note that today there is no guarantee that the original waiter for a
duplicate-inserting xact to complete will be the first one to get a
second chance

ProcLockWakeup() only wakes as many waiters from the head of the queue
as can all be granted the lock without any conflicts. So I don't
think there is a race condition in that path.

Right, but what about XactLockTableWait() itself? It only acquires a
ShareLock on the xid of the got-there-first inserter that potentially
hasn't yet committed/aborted.

That's an interesting point. As you pointed out in later emails, that
cases is handled for heap tuple locks, but btree uniqueness conflicts
are a different kettle of fish.

Yeah, you're right. As I mentioned to Andres already, when row locking
happens and there is this kind of conflict, my approach is to retry
from scratch (go right back to before value lock acquisition) in the
sort of scenario that generally necessitates EvalPlanQual() looping,
or to throw a serialization failure where that's appropriate. After an
unsuccessful attempt at row locking there could well be an interim
wait for another xact to finish, before retrying (at read committed
isolation level). This is why I think that value locking/retrying
should be cheap, and should avoid bloat if at all possible.

Forgive me if I'm making a leap here, but it seems like what you're
saying is that the semantics of upsert that one might naturally expect
are *arguably* fundamentally impossible, because they entail
potentially locking a row that isn't current to your snapshot,

Precisely.

and you cannot throw a serialization failure at read committed.

Not sure that's true, but at least it might not be the most desirable behavior.

I respectfully
suggest that that exact definition of upsert isn't a useful one,
because other snapshot isolation/MVCC systems operating within the
same constraints must have the same issues, and yet they manage to
implement something that could be called upsert that people seem happy
with.

Yeah. I wonder how they do that.

I wouldn't go that far. The number of possible additional primitives
that are useful isn't that high, unless we decide that LWLocks are
going to be a fundamentally different thing, which I consider
unlikely.

I'm not convinced, but we can save that argument for another day.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Mon, Sep 23, 2013 at 12:49 PM, Robert Haas <robertmhaas@gmail.com> wrote:

Right, but what about XactLockTableWait() itself? It only acquires a
ShareLock on the xid of the got-there-first inserter that potentially
hasn't yet committed/aborted.

That's an interesting point. As you pointed out in later emails, that
cases is handled for heap tuple locks, but btree uniqueness conflicts
are a different kettle of fish.

Right.

It suits my purposes to have the value locks be held for only an
instant, because:

1) It will perform much better and deadlock much less in certain
scenarios if sessions are given leeway to not block each other across
multiple values in multiple unique indexes (i.e. we make them
"considerate", like a person with a huge shopping cart that lets
another person with one thing ahead of them in a queue, and perhaps in
doing so greatly reduces their own wait because the guy with one thing
makes the cashier immediately say 'no' to the person with all those
groceries. Ahem). I don't think that this implies any additional
anomalies at read committed, and I'm reasonably confident that this
doesn't regress things to any degree lock starvation wise - lock
starvation can only come from a bunch of inserters of the same value
that consistently abort, just like the present situation with one
unique index (I think it's better with multiple unique indexes than
with only one - more opportunities for the would-be-starved session to
hear a definitive no answer and give up).

2) It will probably be considerably easier if and when we improve on
the buffer locking stuff (by adding a value locking SLRU) to assume
that they'll be shortly held. For example, maybe it's okay that the
implementation doesn't allow page splits on value-locked pages, and
maybe that makes things much easier to reason about. If you're
determined to have a strict serial ordering of value locking *without
serialization failures*, I think what I've already said about the
interactions between row locking and value locking demonstrates that
that's close to or actually impossible. Plus, it would really suck for
performance if that SLRU had to actually swap value locks to and from
disk, which becomes a real possibility if they're really long held
(mere index scans aren't going to keep the cache warm, so the
worst-case latency for an innocent inserter into some narrow range of
values might be really bad).

Speaking of ease of implementation, how do you guarantee that the
value locking waiters get the right to insert in serial order (if
that's something that you value, which I don't at RC)? You have to fix
the same "race" that already exists when acquiring a ShareLock on an
xid, and blocking on value lock acquisition. The only possible remedy
I can see for that is to integrate heap and btree locking in a much
more intimate and therefore sketchy way. You need something like
LockTuple() to arbitrate ordering, but what, and how, and where, and
with how many buffer locks held?

Most importantly:

3) As I've already mentioned, heavy value locks (like promise tuples
or similar schemes, as opposed to actual heavyweight locks)
concomitantly increase the window in which a conflict can be created
for row locking. Most transactions last but an instant, and so the
fact that other session may already be blocked locking on the
would-be-duplicate row perhaps isn't that relevant. Doing all that
clean-up is going to give other sessions increased opportunity to lock
the row themselves, and ruin our day.

But these points are about long held value locks, not the cost of
making their acquisition relatively expensive or inexpensive (but
still more or less instantaneous), so why mention that at all? Well,
since we're blocking everyone else with our value locks, they get to
have a bad day too. All the while, they're perhaps virtually
pre-destined to find some row to lock, but the window for something to
happen to that row for that to conflict with eventual row locking (to
*unnecessarily* conflict, as for example when an innocuous HOT update
occurs) gets larger and larger as they wait longer and longer on value
locks. Loosely speaking, things get multiplicatively worse - total
gridlock is probably possible, with the deadlock detector only
breaking the gridlock up a bit if we get lucky (unless, maybe, if
value locks last until transaction end...which I think is nigh on
impossible anyway).

The bottom line is that long lasting value locks - value locks that
last the duration of a transaction and are acquired serially, while
guaranteeing that the inserter that gets all the value locks needed
itself gets to insert - have the potential to cascade horribly, in
ways that I can only really begin to reason about. That is, they do
*if* we presume that they have the interactions with row locking that
I believe they do, a belief that no one has taken issue with yet.

Even *considering* this is largely academic, though, because without
some kind of miracle guaranteeing serial ordering, a miracle that
doesn't allow for serialization failures and also doesn't seriously
slow down, for example, updates (by making them care about value locks
*before* they do anything, or in the case of HOT updates *at all*),
all of this is _impossible_. So, I say let's just do the
actually-serial-ordering for value lock acquisition with serialization
failures where we're > read committed. I've seriously considered what
it would take to do it any other way so things would work how you and
Andres expect for read committed, and it makes my head hurt, because
apart from seeming unnecessary to me, it also seems completely
hopeless.

Am I being too negative here? Well, I guess that's possible. The fact
is that it's really hard to judge, because all of this is really hard
to reason about. That's what I really don't like about it.

I respectfully
suggest that that exact definition of upsert isn't a useful one,
because other snapshot isolation/MVCC systems operating within the
same constraints must have the same issues, and yet they manage to
implement something that could be called upsert that people seem happy
with.

Yeah. I wonder how they do that.

My guess is that they have some fancy snapshot type that is used by
the equivalent of ModifyTable subplans, that is appropriately paranoid
about the Halloween problem and so on. How that actually might work is
far from clear, but it's a question that I have begun to consider. As
I said, a concern is that it would be in tension with the generalized,
composable syntax, where we don't explicitly have a "special update".
I'd really like to hear other opinions, though.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Mon, Sep 23, 2013 at 12:49 PM, Robert Haas <robertmhaas@gmail.com> wrote:

and you cannot throw a serialization failure at read committed.

Not sure that's true, but at least it might not be the most desirable behavior.

I'm pretty sure that that's totally true. "You don't have to worry
about serialization failures at read committed, except when you do"
seems kind of weak to me. Especially since none of the usual suspects
say the same thing. That said, it sure would be convenient if it
wasn't true!

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Hi,

Various messages are discussing semantics around visibility. I by now
have a hard time keeping track. So let's keep the discussion of the
desired semantics to this thread.

There have been some remarks about serialization failures in read
committed transactions. I agree, those shouldn't occur. But I don't
actually think they are so much of a problem if we follow the path set
by existing uses of the EPQ logic. The scenario described seems to be an
UPSERT conflicting with a row it cannot see in the original snapshot of
the query.
In that case I think we just have to follow the example laid by
ExecUpdate, ExecDelete and heap_lock_tuple. Use the EPQ machinery (or an
alternative approach with similar enough semantics) to get a new
snapshot and follow the ctid chain. When we've found the end of the
chain we try to update that tuple.
That surely isn't free of surprising semantics, but it would follows existing
semantics. Which everybody writing concurrent applications in read
committed should (but doesn't) know. Adding a different set of semantics
seems like a bad idea.
Robert seems to have been the primary sceptic around this, what scenario
are you actually concerned about?

There are some scenarios that doesn't trivially answer. But I'd like to
understand the primary concerns first.

Regards,

Andres

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Mon, Sep 23, 2013 at 7:05 PM, Peter Geoghegan <pg@heroku.com> wrote:

It suits my purposes to have the value locks be held for only an
instant, because:

[ detailed explanation ]

I don't really disagree with any of that. TBH, I think the question
of how long value locks (as you call them) are held is going to boil
down to a question of how they end up being implemented. As I
mentioned to you at PG Open (going through the details here for those
following along at home), we could optimistically insert the new heap
tuple, then go add index entries for it, and if we find a conflict,
then instead of erroring out, we mark the tuple we were inserting dead
and go try update the conflicting tuple instead. In that
implementation, if we find that we have to wait for some other
transaction along the way, it's probably not worth reversing out the
index entries already inserted, because getting them into the index in
the first place was a WAL-logged operation, and therefore relatively
expensive, and IMHO it's most likely better to just hope things work
out than to risk having to redo all of that.

On the other hand, if the locks are strictly in-memory, then the cost
of releasing them all before we go to wait, and of reacquiring them
after we finish waiting, is pretty low. There might be some
modularity issues to work through there, but they might not turn out
to be very painful, and the advantages you mention are certainly worth
accruing if it turns out to be fairly straightforward.

Personally, I think that trying to keep it all in-memory is going to
be hard. The problem is that we can't de-optimize regular inserts or
updates to any significant degree to cater to this feature - because
as valuable as this feature is, the number of times it gets used is
still going to be a whole lot smaller than the number of times it
doesn't get used. Also, I tend to think that we might want to define
the operation as a REPLACE-type operation with respect to a certain
set of key columns; and so we'll do the insert-or-update behavior with
respect only to the index on those columns and let the chips fall
where they may with respect to any others. In that case this all
becomes much less urgent.

Even *considering* this is largely academic, though, because without
some kind of miracle guaranteeing serial ordering, a miracle that
doesn't allow for serialization failures and also doesn't seriously
slow down, for example, updates (by making them care about value locks
*before* they do anything, or in the case of HOT updates *at all*),
all of this is _impossible_. So, I say let's just do the
actually-serial-ordering for value lock acquisition with serialization
failures where we're > read committed. I've seriously considered what
it would take to do it any other way so things would work how you and
Andres expect for read committed, and it makes my head hurt, because
apart from seeming unnecessary to me, it also seems completely
hopeless.

Am I being too negative here? Well, I guess that's possible. The fact
is that it's really hard to judge, because all of this is really hard
to reason about. That's what I really don't like about it.

Suppose we define the operation as REPLACE rather than INSERT...ON
DUPLICATE KEY LOCK FOR UPDATE. Then we could do something like this:

1. Try to insert a tuple. If no unique index conflicts occur, stop.
2. Note the identity of the conflicting tuple and mark the inserted
heap tuple dead.
3. If the conflicting tuple's inserting transaction is still in
progress, wait for the inserting transaction to end.
4. If the conflicting tuple is dead (e.g. because the inserter
aborted), start over.
5. If the conflicting tuple's key columns no longer match the key
columns of the REPLACE operation, start over.
6. If the conflicting tuple has a valid xmax, wait for the deleting or
locking transaction to end. If xmax is still valid, follow the CTID
chain to the updated tuple, let that be the new conflicting tuple, and
resume from step 5.
7. Update the tuple, even though it may be invisible to our snapshot
(a deliberate MVCC violation!).

While this behavior is admittedly wonky from an MVCC perspective, I
suspect that it would make a lot of people happy.

I respectfully
suggest that that exact definition of upsert isn't a useful one,
because other snapshot isolation/MVCC systems operating within the
same constraints must have the same issues, and yet they manage to
implement something that could be called upsert that people seem happy
with.

Yeah. I wonder how they do that.

My guess is that they have some fancy snapshot type that is used by
the equivalent of ModifyTable subplans, that is appropriately paranoid
about the Halloween problem and so on. How that actually might work is
far from clear, but it's a question that I have begun to consider. As
I said, a concern is that it would be in tension with the generalized,
composable syntax, where we don't explicitly have a "special update".
I'd really like to hear other opinions, though.

The tension here feels fairly fundamental to me; I don't think our
implementation is to blame. I think the problem isn't so much to
figure out a clever trick that will make this all work in a truly
elegant fashion as it is to decide exactly how we're going to
compromise MVCC semantics in the least blatant way.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Sep 24, 2013 at 5:14 AM, Andres Freund <andres@2ndquadrant.com> wrote:

Various messages are discussing semantics around visibility. I by now
have a hard time keeping track. So let's keep the discussion of the
desired semantics to this thread.

There have been some remarks about serialization failures in read
committed transactions. I agree, those shouldn't occur. But I don't
actually think they are so much of a problem if we follow the path set
by existing uses of the EPQ logic. The scenario described seems to be an
UPSERT conflicting with a row it cannot see in the original snapshot of
the query.
In that case I think we just have to follow the example laid by
ExecUpdate, ExecDelete and heap_lock_tuple. Use the EPQ machinery (or an
alternative approach with similar enough semantics) to get a new
snapshot and follow the ctid chain. When we've found the end of the
chain we try to update that tuple.
That surely isn't free of surprising semantics, but it would follows existing
semantics. Which everybody writing concurrent applications in read
committed should (but doesn't) know. Adding a different set of semantics
seems like a bad idea.
Robert seems to have been the primary sceptic around this, what scenario
are you actually concerned about?

I'm not skeptical about offering it as an option; in fact, I just
suggested basically the same thing on the other thread, before reading
this. Nonetheless it IS an MVCC violation; the chances that someone
will be able to demonstrate serialization anomalies that can't occur
today with this new facility seem very high to me. I feel it's
perfectly fine to respond to that by saying: yep, we know that's
possible, if it's a concern in your environment then don't use this
feature. But it should be clearly documented.

I do think that it will be easier to get this to work if we have a
define the operation as REPLACE, bundling all of the magic inside a
single SQL command. If the user issues an INSERT first and then must
try an UPDATE afterwards if the INSERT doesn't actually insert, then
you're going to have problems if the UPDATE can't see the tuple with
which the INSERT conflicted, and you're going to need some kind of a
loop in case the UPDATE itself fails. Even if we can work out all the
details, a single command that does insert-or-update seems like it
will be easier to use and more efficient. You might also want to
insert multiple tuples using INSERT ... VALUES (...), (...), (...);
figuring out which ones were inserted and which ones must now be
updated seems like a chore better avoided.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Sep 24, 2013 at 7:35 AM, Robert Haas <robertmhaas@gmail.com> wrote:

I don't really disagree with any of that. TBH, I think the question
of how long value locks (as you call them) are held is going to boil
down to a question of how they end up being implemented.

Well, I think we can rule out value locks that are held for the
duration of a transaction right away. That's just not going to fly.

As I mentioned to you at PG Open (going through the details here for those
following along at home), we could optimistically insert the new heap
tuple, then go add index entries for it, and if we find a conflict,
then instead of erroring out, we mark the tuple we were inserting dead
and go try update the conflicting tuple instead. In that
implementation, if we find that we have to wait for some other
transaction along the way, it's probably not worth reversing out the
index entries already inserted, because getting them into the index in
the first place was a WAL-logged operation, and therefore relatively
expensive, and IMHO it's most likely better to just hope things work
out than to risk having to redo all of that.

I'm afraid that there are things that concern me about this design. It
does have one big advantage over promise-tuples, which is that the
possibility of index-only bloat, and even the possible need to freeze
indexes separately from their heap relation is averted (or are you
going to have recovery do promise clean-up instead? Does recovery look
for an eventual successful insertion relating to the promise? How far
does it look?). However, while I'm just as concerned as you that
backing out is too expensive, I'm equally concerned that there is no
reasonable alternative to backing out, which is why cheap, quick
in-memory value locks are so compelling to me. See my remarks below.

On the other hand, if the locks are strictly in-memory, then the cost
of releasing them all before we go to wait, and of reacquiring them
after we finish waiting, is pretty low. There might be some
modularity issues to work through there, but they might not turn out
to be very painful, and the advantages you mention are certainly worth
accruing if it turns out to be fairly straightforward.

It's certainly a difficult situation to judge.

Personally, I think that trying to keep it all in-memory is going to
be hard. The problem is that we can't de-optimize regular inserts or
updates to any significant degree to cater to this feature - because
as valuable as this feature is, the number of times it gets used is
still going to be a whole lot smaller than the number of times it
doesn't get used.

Right - I don't think that anyone would argue that any other standard
should be applied. Fortunately, I'm reasonably confident that it can
work. The last part of index tuple insertion, where we acquire an
exclusive lock on a buffer, needs to look out for a page header bit
(on pages considered for insertion of its value). The cost of that to
anyone not using this feature is likely to be infinitesimally small.
We can leave clean-up of that bit to the next inserter, who needs the
exclusive lock anyway and doesn't find a corresponding SLRU entry. But
really, that's a discussion for another day. I think we'd want to
track value locks per pinned-by-upserter buffer, to localize any
downsides on concurrency. If we forbid page-splits in respect of a
value-locked page, we can still have a stable value (buffer number) to
use within a shared memory hash table, or something along those lines.
We're still going to want to minimize the duration of locking under
this scheme, by doing TOASTing before locking values and so on, which
is quite possible.

If we're really lucky, maybe the value locking stuff can be
generalized or re-used as part of a btree index insertion buffer
feature.

Also, I tend to think that we might want to define
the operation as a REPLACE-type operation with respect to a certain
set of key columns; and so we'll do the insert-or-update behavior with
respect only to the index on those columns and let the chips fall
where they may with respect to any others. In that case this all
becomes much less urgent.

Well, MySQL's REPLACE does zero or more DELETEs followed by an INSERT,
not try an INSERT, then maybe mark the heap tuple if there's a unique
index dup and then go UPDATE the conflicting tuple. I mention this
only because the term REPLACE has a certain baggage, and I feel it's
important to be careful about such things.

The only way that's going to work is if you say "use this unique
index", which will look pretty gross in DML. That might actually be
okay with me if we had somewhere to go from there in a future release,
but I doubt that's the case. Another issue is that I'm not sure that
this helps Andres much (or rather, clients of the logical changeset
generation infrastructure that need to do conflict resolution), and
that matters a lot to me here.

Suppose we define the operation as REPLACE rather than INSERT...ON
DUPLICATE KEY LOCK FOR UPDATE. Then we could do something like this:

1. Try to insert a tuple. If no unique index conflicts occur, stop.
2. Note the identity of the conflicting tuple and mark the inserted
heap tuple dead.
3. If the conflicting tuple's inserting transaction is still in
progress, wait for the inserting transaction to end.

Sure, this is basically what the code does today (apart from marking a
just-inserted tuple dead).

4. If the conflicting tuple is dead (e.g. because the inserter
aborted), start over.

Start over from where? I presume you mean the index tuple insertion,
as things are today. Or do you mean the very start?

5. If the conflicting tuple's key columns no longer match the key
columns of the REPLACE operation, start over.

What definition of equality or inequality? I think you're going to
have to consider stashing information about the btree operator class,
which seems not ideal - a modularity violation beyond what we already
do in, say, execQual.c, I think. I think in general we have to worry
about the distinction between a particular btree operator class's idea
of equality (doesn't have to be = operator), that exists for a
particular index, and some qual's idea of equality. It would probably
be quite invasive to fix this, which I for one would find hard to
justify.

I think my scheme is okay here while yours isn't, because mine
involves row locking only, and hoping that nothing gets updated in
that tiny window after transaction commit - if it doesn't, that's good
enough for us, because we know that the btree code's opinion still
holds - if I'm not mistaken, *nothing* can have changed to the logical
row without us hearing about it (i.e. without heap_lock_tuple()
returning HeapTupleUpdated). On the other hand, you're talking about
concluding that something is not a duplicate in a way that needs to
satisfy btree unique index equality (so whatever operator is
associated with btree strategy number 3, equality, for some particular
unique index with some particular operator class) and not necessarily
just a qual written with a potentially distinct notion of equality in
respect of the relevant unique-constrained datums.

Maybe you can solve this one problem, but the fact remains that to do
so would be a pretty bad modularity violation, even by the standards
of the existing btree code. That's the basic reason why I'm averse to
using EvalPlanQual() in this fashion, or in a similar fashion. Even if
you solve all the problems for btree, I can't imagine what type of
burden it puts on amcanunique AM authors generally - I know at least
one person who won't be happy with that. :-)

6. If the conflicting tuple has a valid xmax, wait for the deleting or
locking transaction to end. If xmax is still valid, follow the CTID
chain to the updated tuple, let that be the new conflicting tuple, and
resume from step 5.

So you've arbitrarily restricted us to one value lock and one row lock
per REPLACE slot processed, which sort of allows us to avoid solving
the basic problem of value locking, because it isn't too bad now - no
need to backtrack across indexes. Clean-up (marking the heap tuple
dead) is much more expensive than releasing locks in memory (although
much less expensive than promise tuple killing), but needing to
clean-up is maybe less likely because conflicts can only come from one
unique index. Has this really bought us anything, though? Consider
that conflicts are generally only expected on one unique index anyway.
Plus you still have the disconnect between value and row locking, as
far as I can tell - "start from scratch" remains a possible step until
very late, except you pay a lot more for clean-up - avoiding that
expensive clean-up is the major benefit of introducing an SLRU-based
shadow value locking scheme to the btree code. I don't see that there
is a way to deal with the value locking/row locking disconnect other
than to live with it in a smart way.

Anyway, your design probably avoids the worst kind of gridlock. Let's
assume that it works out -- my next question has to be, where can we
go from there?

7. Update the tuple, even though it may be invisible to our snapshot
(a deliberate MVCC violation!).

I realize that you just wanted to sketch a design, but offhand I think
that the basic problem with what you describe is that it isn't
accepting of the inevitability of there being a disconnect between
value and row locking. Also, this doesn't fit with any roadmap for
getting a real upsert, and compromises the conceptual integrity of the
AM in a way that isn't likely to be accepted, and, at the risk of
saying too much before you've defended your design, perhaps even
necessitates invasive changes to the already extremely complicated row
locking code.

While this behavior is admittedly wonky from an MVCC perspective, I
suspect that it would make a lot of people happy.

"Wonky from an MVCC perspective" is the order of the day here. :-)

My guess is that they have some fancy snapshot type that is used by
the equivalent of ModifyTable subplans, that is appropriately paranoid
about the Halloween problem and so on. How that actually might work is
far from clear, but it's a question that I have begun to consider. As
I said, a concern is that it would be in tension with the generalized,
composable syntax, where we don't explicitly have a "special update".
I'd really like to hear other opinions, though.

The tension here feels fairly fundamental to me; I don't think our
implementation is to blame. I think the problem isn't so much to
figure out a clever trick that will make this all work in a truly
elegant fashion as it is to decide exactly how we're going to
compromise MVCC semantics in the least blatant way.

Yeah, I totally understand the problem that way. I think it would be a
bit of a pity to give up the composability, which I liked, but it's
something that we'll have to consider. On the other hand, perhaps we
can get away with it - we simply don't know enough yet.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Sat, Sep 21, 2013 at 05:07:11PM -0700, Peter Geoghegan wrote:

In the average/uncontended case, the subxact example bloats less than
all alternatives to my design proposed to date (including the "unborn
heap tuple" idea Robert mentioned in passing to me in person the other
day, which I think is somewhat similar to a suggestion of Heikki's
[1]). The average case is very important, because in general
contention usually doesn't happen.

This thread had a lot of discussion about bloating. I wonder, does the
code check to see if there is a matching row _before_ adding any data?
Our test-and-set code first checks to see if the lock is free, then if
it it is, it locks the bus and does a test-and-set. Couldn't we easily
check the indexes for matches before doing any locking? It seems that
would avoid bloat in most cases, and allow for a simpler implementation.

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ It's impossible for everything to be true. +

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Sep 25, 2013 at 8:19 PM, Bruce Momjian <bruce@momjian.us> wrote:

This thread had a lot of discussion about bloating. I wonder, does the
code check to see if there is a matching row _before_ adding any data?

That's pretty much what the patch does.

Our test-and-set code first checks to see if the lock is free, then if
it it is, it locks the bus and does a test-and-set. Couldn't we easily
check the indexes for matches before doing any locking? It seems that
would avoid bloat in most cases, and allow for a simpler implementation.

The value locks are only really necessary for getting consensus across
unique indexes on whether or not to go forward, and to ensure that
insertion can *finish* unhindered once we're sure that's appropriate.
Once we've committed to insertion, we hold them across heap tuple
insertion and release each value lock as part of something close to
conventional btree index tuple insertion (with an index tuple with an
ordinary heap pointer inserted). I believe that all schemes proposed
to date have some variant of what could be described as value locking,
such as ordinary index tuples inserted speculatively.

Value locks are *not* held during row locking, and an attempt at row
locking is essentially opportunistic for various reasons (it boils
down to the fact that re-verifying uniqueness outside of the btree
code is very unappealing, and in any case would naturally sometimes be
insufficient - what happens if key values change across row
versions?). This might sound a bit odd, but is in a sense no different
to the current state of affairs, where the first waiter on a blocking
xact that inserted a would-be duplicate is not guaranteed to be the
first to get a second chance at inserting. I don't believe that there
are any significant additional lock starvation hazards.

In the simple case where there is a conflicting tuple that's already
committed, value locks above and beyond what the btree code does today
are unnecessary (provided the attempt to acquire a row lock is
eventually successful, which mostly means that no one else has
updated/deleted - otherwise we try again).

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Sep 25, 2013 at 08:48:11PM -0700, Peter Geoghegan wrote:

On Wed, Sep 25, 2013 at 8:19 PM, Bruce Momjian <bruce@momjian.us> wrote:

This thread had a lot of discussion about bloating. I wonder, does the
code check to see if there is a matching row _before_ adding any data?

That's pretty much what the patch does.

So, I guess my question is if we are only bloating on a contended
operation, do we expect that to happen so much that bloat is a problem?

I think the big objection to the patch is the additional code complexity
and the potential to slow down other sessions. If it is only bloating
on a contended operation, are these two downsides worth avoiding the
bloat?

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ It's impossible for everything to be true. +

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Thu, Sep 26, 2013 at 07:43:15AM -0400, Bruce Momjian wrote:

On Wed, Sep 25, 2013 at 08:48:11PM -0700, Peter Geoghegan wrote:

On Wed, Sep 25, 2013 at 8:19 PM, Bruce Momjian <bruce@momjian.us> wrote:

This thread had a lot of discussion about bloating. I wonder, does the
code check to see if there is a matching row _before_ adding any data?

That's pretty much what the patch does.

So, I guess my question is if we are only bloating on a contended
operation, do we expect that to happen so much that bloat is a problem?

I think the big objection to the patch is the additional code complexity
and the potential to slow down other sessions. If it is only bloating
on a contended operation, are these two downsides worth avoiding the
bloat?

Also, this isn't like the case where we are incrementing sequences --- I
am unclear what workload is going to cause a lot of contention. If two
sessions try to insert the same key, there will be bloat, but later
upsert operations will already see the insert and not cause any bloat.

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ It's impossible for everything to be true. +

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Thu, Sep 26, 2013 at 4:43 AM, Bruce Momjian <bruce@momjian.us> wrote:

So, I guess my question is if we are only bloating on a contended
operation, do we expect that to happen so much that bloat is a problem?

Maybe I could have done a better job of explaining the nature of my
concerns around bloat.

I am specifically concerned about bloat and the clean-up of bloat that
occurs between (or during) value locking and eventual row locking,
because of the necessarily opportunistic nature of the way we go from
one to the other. Bloat, and the obligation to clean it up
synchronously, make row lock conflicts more likely. Conflicts make
bloat more likely, because a conflict implies that another iteration,
complete with more bloat, is necessary.

When you consider that the feature will frequently be used with the
assumption that updating is a much more likely outcome, it becomes
clear that we need to be careful about this sort of interplay.

Having said all that, I would have no objection to some reasonable,
bound amount of bloat occurring elsewhere if that made sense. For
example, I'd certainly be happy to consider the question of whether or
not it's worth doing a kind of speculative heap insertion before
acquiring value locks, because that doesn't need to happen again and
again in the same, critical place, in the interim between value
locking and row locking. The advantage of doing that particular thing
would be to reduce the duration that value locks are held - the
disadvantages would be the *usual* disadvantages of bloat. However,
this is obviously a premature discussion to have now, because the
eventual exact nature of value locks are not known.

I think the big objection to the patch is the additional code complexity
and the potential to slow down other sessions. If it is only bloating
on a contended operation, are these two downsides worth avoiding the
bloat?

I believe that all other schemes proposed have some degree of bloat
even in the uncontended case, because they optimistically assume than
an insert will occur, when in general an update is perhaps just as
likely, and will bloat just the same. So, as I've said before,
definition of uncontended is important here.

There is no reason to assume that alternative proposals will affect
concurrency any less than my proposal - the buffer locking thing
certainly isn't essential to my design. You need to weigh things like
WAL-logging multiples times, that other proposals have. You're right
to say that all of this is complex, but I really think that quite
apart from anything else, my design is simpler than others. For
example, the design that Robert sketched would introduce a fairly
considerable modularity violation, per my recent remarks to him, and
actually plastering over that would be a considerable undertaking.
Now, you might counter, "but those other designs haven't been worked
out enough". That's true, but then my efforts to work them out further
by pointing out problems with them haven't gone very far. I have
sincerely tried to see a way to make them work.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Sep 24, 2013 at 10:15 PM, Peter Geoghegan <pg@heroku.com> wrote:

Well, I think we can rule out value locks that are held for the
duration of a transaction right away. That's just not going to fly.

I think I agree with that. I don't think I remember hearing that proposed.

If we're really lucky, maybe the value locking stuff can be
generalized or re-used as part of a btree index insertion buffer
feature.

Well, that would be nifty.

Also, I tend to think that we might want to define
the operation as a REPLACE-type operation with respect to a certain
set of key columns; and so we'll do the insert-or-update behavior with
respect only to the index on those columns and let the chips fall
where they may with respect to any others. In that case this all
becomes much less urgent.

Well, MySQL's REPLACE does zero or more DELETEs followed by an INSERT,
not try an INSERT, then maybe mark the heap tuple if there's a unique
index dup and then go UPDATE the conflicting tuple. I mention this
only because the term REPLACE has a certain baggage, and I feel it's
important to be careful about such things.

I see. Well, we could try to mimic their semantics, I suppose. Those
semantics seem like a POLA violation to me; who would have thought
that a REPLACE could delete multiple tuples? But what do I know?

The only way that's going to work is if you say "use this unique
index", which will look pretty gross in DML. That might actually be
okay with me if we had somewhere to go from there in a future release,
but I doubt that's the case. Another issue is that I'm not sure that
this helps Andres much (or rather, clients of the logical changeset
generation infrastructure that need to do conflict resolution), and
that matters a lot to me here.

Yeah, it's kind of awful.

Suppose we define the operation as REPLACE rather than INSERT...ON
DUPLICATE KEY LOCK FOR UPDATE. Then we could do something like this:

1. Try to insert a tuple. If no unique index conflicts occur, stop.
2. Note the identity of the conflicting tuple and mark the inserted
heap tuple dead.
3. If the conflicting tuple's inserting transaction is still in
progress, wait for the inserting transaction to end.

Sure, this is basically what the code does today (apart from marking a
just-inserted tuple dead).

4. If the conflicting tuple is dead (e.g. because the inserter
aborted), start over.

Start over from where? I presume you mean the index tuple insertion,
as things are today. Or do you mean the very start?

Yes, that's what I meant.

5. If the conflicting tuple's key columns no longer match the key
columns of the REPLACE operation, start over.

What definition of equality or inequality?

Binary equality, same as we'd use to decide whether an update can be done HOT.

7. Update the tuple, even though it may be invisible to our snapshot
(a deliberate MVCC violation!).

I realize that you just wanted to sketch a design, but offhand I think
that the basic problem with what you describe is that it isn't
accepting of the inevitability of there being a disconnect between
value and row locking. Also, this doesn't fit with any roadmap for
getting a real upsert,

Well, there are two separate issues here: what to do about MVCC, and
how to do the locking. From an MVCC perspective, I can think of only
two behaviors when the conflicting tuple is committed but invisible:
roll back, or update it despite it being invisible. If you're saying
you don't like either of those choices, I couldn't agree more, but I
don't have a third idea. If you do, I'm all ears.

In terms of how to do the locking, what I'm mostly saying is that we
could try to implement this in a way that invents as few new concepts
as possible. No promise tuples, no new SLRU, no new page-level bits,
just index tuples and heap tuples and so on. Ideally, we don't even
change the WAL format, although step 2 might require a new record
type. To the extent that what I actually described was at variance
with that goal, consider it a defect in my explanation rather than an
intent to vary. I think there's value in considering such an
implementation because each new thing that we have to introduce in
order to get this feature is a possible reason for it to be rejected -
for modularity reasons, or because it hurts performance elsewhere, or
because it's more code we have to maintain, or whatever.

Now, what I hear you saying is, gee, the performance of that might be
terrible. I'm not sure that I believe that, but it's possible that
you're right. Much seems to depend on what you think the frequency of
conflicts will be, and perhaps I'm assuming it will be low while
you're assuming a higher value. Regardless, if the performance of the
sort of implementation I'm talking about would be terrible (under some
agreed-upon definition of what terrible means in this context), then
that's a good argument for not doing it that way. I'm just not
convinced that's the case.

Basically, if there's a way we can do this without changing the
on-disk format (even in a backward-compatible way), I'd be strongly
inclined to go that route unless we have a really compelling reason to
believe it's going to suck (or be outright impossible).

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Thu, Sep 26, 2013 at 3:07 PM, Peter Geoghegan <pg@heroku.com> wrote:

When you consider that the feature will frequently be used with the
assumption that updating is a much more likely outcome, it becomes
clear that we need to be careful about this sort of interplay.

I think one thing that's pretty clear at this point is that almost any
version of this feature could be optimized for either the insert case
or the update case. For example, my proposal could be modified to
search for a conflicting tuple first, potentially wasting an index
probes (or multiple index probes, if you want to search for potential
conflicts in multiple indexes) if we're inserting, but winning heavily
in the update case. As written, it's optimized for the insert case.

In fact, I don't know how to know which of these things we should
optimize for. I wrote part of the code for an EDB proprietary feature
that can do insert-or-update loads about 6 months ago[1]In case you're wondering, attempting to use that feature to upsert an invisible tuple will result in the load failing with a unique index violation., and we
optimized it for updates. That was not, however, a matter of
principal; it just turned out to be easier to implement that way. In
fact, I would have assumed that the insert-mostly case was more
likely, but I think the real answer is that some environments will be
insert-mostly and some will be update-mostly and some will be a mix.

If we really want to squeeze out every last drop of possible
performance, we might need two modes: one that assumes we'll mostly
insert, and another that assumes we'll mostly update. That seems a
frustrating amount of detail to have to expose to the user; an
implementation that was efficient in both cases would be very
desirable, but I do not have a good idea how to get there.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

[1]: In case you're wondering, attempting to use that feature to upsert an invisible tuple will result in the load failing with a unique index violation.
an invisible tuple will result in the load failing with a unique index
violation.

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Thu, Sep 26, 2013 at 03:33:34PM -0400, Robert Haas wrote:

On Thu, Sep 26, 2013 at 3:07 PM, Peter Geoghegan <pg@heroku.com> wrote:

When you consider that the feature will frequently be used with the
assumption that updating is a much more likely outcome, it becomes
clear that we need to be careful about this sort of interplay.

I think one thing that's pretty clear at this point is that almost any
version of this feature could be optimized for either the insert case
or the update case. For example, my proposal could be modified to
search for a conflicting tuple first, potentially wasting an index
probes (or multiple index probes, if you want to search for potential
conflicts in multiple indexes) if we're inserting, but winning heavily
in the update case. As written, it's optimized for the insert case.

I assumed the code was going to do the index lookups first without a
lock, and take the appropriate action, insert or update, with fallbacks
for guessing wrong.

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ It's impossible for everything to be true. +

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Thu, Sep 26, 2013 at 12:15 PM, Robert Haas <robertmhaas@gmail.com> wrote:

Well, I think we can rule out value locks that are held for the
duration of a transaction right away. That's just not going to fly.

I think I agree with that. I don't think I remember hearing that proposed.

I think I might have been unclear - I mean locks that are held for the
duration of *another* transaction, not our own, as we wait for that
other transaction to commit/abort. I think that earlier remarks from
yourself and Andres implied that this would be necessary. Perhaps I'm
mistaken. Your most recent design proposal doesn't do this, but I
think that that's only because it restricts the user to a single
unique index - it would otherwise be necessary to sit on the earlier
value locks (index tuples belonging to an unfinished transaction)
pending the completion of some other conflicting transaction, which
has numerous disadvantages (as described in my "it suits my purposes
to have the value locks be held for only an instant" mail to you [1]/messages/by-id/CAM3SWZRV0F-DjgpXu-WxGoG9eEcLawNrEiO5+3UKRp2e5s=TSg@mail.gmail.com).

If we're really lucky, maybe the value locking stuff can be
generalized or re-used as part of a btree index insertion buffer
feature.

Well, that would be nifty.

Yes, it would. I think, based on a conversation with Rob Wultsch, that
it's another area where MySQL still do quite a bit better.

I see. Well, we could try to mimic their semantics, I suppose. Those
semantics seem like a POLA violation to me; who would have thought
that a REPLACE could delete multiple tuples? But what do I know?

I think that it's fairly widely acknowledged to not be very good.
Every MySQL user uses INSERT...ON DUPLICATE KEY UPDATE instead.

The only way that's going to work is if you say "use this unique
index", which will look pretty gross in DML.

Yeah, it's kind of awful.

It is.

What definition of equality or inequality?

Binary equality, same as we'd use to decide whether an update can be done HOT.

I guess that's acceptable in theory, because binary equality is
necessarily a *stricter* condition than equality according to some
operator that is an equivalence relation. But the fact remains that
you're just ameliorating the problem by making it happen less often
(both through this kind of trick, but also by restricting us to one
unique index), not actually fixing it.

Well, there are two separate issues here: what to do about MVCC, and
how to do the locking.

Totally agreed. Fortunately, unlike the different aspects of value and
row locking, I think that these two questions can be reasonable
considered independently.

From an MVCC perspective, I can think of only
two behaviors when the conflicting tuple is committed but invisible:
roll back, or update it despite it being invisible. If you're saying
you don't like either of those choices, I couldn't agree more, but I
don't have a third idea. If you do, I'm all ears.

I don't have another idea either. In fact, I'd go so far as to say
that doing any third thing that's better than those two to any
reasonable person is obviously impossible. But I'd add that we simple
cannot rollback at read committed, so we're just going to have to hold
our collective noses and do strange things with visibility.

FWIW, I'm tentatively looking at doing something like this:

*************** HeapTupleSatisfiesMVCC(HeapTuple htup, S
*** 958,963 ****
--- 959,975 ----
  * By here, the inserting transaction has committed - have to check
  * when...
  */
+
+ /*
+ * Not necessarily visible to snapshot under conventional MVCC rules, but
+ * still locked by our xact and not updated -- importantly, normal MVCC
+ * semantics apply when we update the row, so only one version will be
+ * visible at once
+ */
+ if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask) &&
+ TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple)))
+ return true;
+
  if (XidInMVCCSnapshot(HeapTupleHeaderGetXmin(tuple), snapshot))
  return false; /* treat as still in progress */

This is something that I haven't given remotely enough thought yet, so
please take it with a big grain of salt.

In terms of how to do the locking, what I'm mostly saying is that we
could try to implement this in a way that invents as few new concepts
as possible. No promise tuples, no new SLRU, no new page-level bits,
just index tuples and heap tuples and so on. Ideally, we don't even
change the WAL format, although step 2 might require a new record
type. To the extent that what I actually described was at variance
with that goal, consider it a defect in my explanation rather than an
intent to vary. I think there's value in considering such an
implementation because each new thing that we have to introduce in
order to get this feature is a possible reason for it to be rejected -
for modularity reasons, or because it hurts performance elsewhere, or
because it's more code we have to maintain, or whatever.

There is certainly value in considering that, and you're right to take
that tact - it is generally valuable to have a patch be minimally
invasive. However, ultimately that's just one aspect of any given
design, an aspect that needs to be weighed against others where there
is a tension. Obviously in this instance I believe, rightly or
wrongly, that doing more - adding more infrastructure than might be
considered strictly necessary - is the least worst thing. Also,
sometimes the apparent similarity of a design to what we have today is
illusory - certainly, I think you'd at least agree that the problems
that bloating during the interim between value locking and row locking
present are qualitatively different to other problems that bloat
presents in all existing scenarios.

FWIW I'm not doing things this way because I'm ambitious, and am
willing to risk not having my work accepted if that means I might get
something that performs better, or has more features (like not
requiring the user to specify a unique index in DML). Rather, I'm
doing things this way because I sincerely believe that on balance mine
is the best, most forward-thinking design proposed to date, and
therefore the design most likely to ultimately be accepted (even
though I do of course accept that there are numerous aspects that need
to be worked out still). If the whole design is ultimately not
accepted, that's something that I'll have to deal with, but understand
that I don't see any way to play it safe here (except, I suppose, to
give up now).

Now, what I hear you saying is, gee, the performance of that might be
terrible. I'm not sure that I believe that, but it's possible that
you're right.

I think that the average case will be okay, but not great. I think
that the worst case performance may well be unforgivably bad, and it's
a fairly plausible worst case. Even if someone disputes its
likelihood, and demonstrates that it isn't actually that likely, that
isn't necessarily very re-assuring - getting all the details right is
pretty subtle, especially compared to just not bloating, and just
deferring to the btree code whose responsibilities include enforcing
uniqueness.

Much seems to depend on what you think the frequency of
conflicts will be, and perhaps I'm assuming it will be low while
you're assuming a higher value. Regardless, if the performance of the
sort of implementation I'm talking about would be terrible (under some
agreed-upon definition of what terrible means in this context), then
that's a good argument for not doing it that way. I'm just not
convinced that's the case.

All fair points. Forgive me for repeating myself, but the word
"conflict" needs to be used carefully here, because there are two
basic ways of interpreting it - something that happens due to
concurrent xact activity around the same values, and something that
happens due to there already being some row there with a conflicting
value from some time ago (or that our xact inserted, even). Indeed,
the former *is* generally much less likely than the latter, so the
distinction is important. You could also further differentiate between
value level and row level conflicts, or at least I think that you
should, and that we should allow for value level conflicts.

Let me try and explain myself better, with reference to a concrete
example. Suppose we have a table with a primary key column, A, and a
unique constraint column, B, and we lock the pk value first and the
unique constraint value second. I'm assuming your design, but allowing
for multiple unique indexes because I don't think doing anything less
will be accepted - promise tuples have some of the same problems, as
well as some other idiosyncratic ones (see my earlier remarks on
recovery/freezing [2]/messages/by-id/CAM3SWZQUUuYYcGksVytmcGqACVMkf1ui1uvfJekM15YkWZpzhw@mail.gmail.com -- Peter Geoghegan for examples of those).

So there is a fairly high probability that the pk value on A will be
unique, and a fairly low probability that the unique constraint value
on B will be unique, at least in this usage pattern of interest, where
the user is mostly going to end up updating. Mostly, we insert a
speculative regular index tuple (that points to a speculative heap
tuple that we might decide to kill) into the pk column, A, right away,
and then maybe block pending the resolution of a conflicting
transaction on the unique constraint column B. I don't think we have
any reasonable way of not blocking on A - if we go clean it up for the
wait, that's going to bloat quite dramatically, *and* we have to WAL
log. In any case you seemed to accept that cleaning up bloat
synchronously like that was just going to be too expensive. So I
suppose that rules that out. That just leaves sitting on the "value
lock" (that the pk index tuple already inserted effectively is)
indefinitely, pending the outcome of the first transaction.

What are the consequences of sitting on that value lock indefinitely?
Well, xacts are going to block on the pk value much more frequently,
by simple virtue of the fact that the value locks there are held for a
long time - they just needed to hear a "no" answer, which the unique
constraint was in most cases happy to immediately give, so this is
totally unnecessary. Contention is now in a certain sense almost as
bad for every unique index as it is for the weakest link. That's only
where the problems begin, though, and it isn't necessary for there to
be bad contention on more than one unique index (the pk could just be
on a serial column, say) to see bad effects.

So your long-running xact that's blocking all the other sessions on
its proposed value for a (or maybe even b) - that finally gets to
proceed. Regardless of whether it commits or aborts, there will be a
big bloat race. This is because when the other sessions get the
go-ahead to proceed, they'll all run to get the row lock (one guy
might insert instead). Only one will be successful, but they'll all
kill their heap tuple on the assumption that they'll probably lock the
row, which is only true in the average case. Now, maybe you can teach
them to not bother killing the heap tuple when there are no index
tuples actually inserted to ruin things, but then maybe not, and maybe
it wouldn't help in this instance if you did teach them (because
there's a third, otherwise irrelevant constraint or whatever).

Realize you can generally only kill the heap tuple *before* you have
the row lock, because otherwise a totally innocent non-HOT update (may
not update any unique indexed columns at all) will deadlock with your
session, which I don't think is defensible, and will probably happen
often if allowed to (after all, this is upsert - users are going to
want to update their locked rows!).

So in this scenario, each of the original blockers will simultaneously
try again and again to get the row lock as one transaction proceeds
with locking and then probably commits. For every blocker's iteration
(there will be n_blockers - 1 iterations, with each iteration
resolving things for one blocker only), each blocker bloats. We're
talking about creating duplicates in unique indexes for each and every
iteration, for each and every blocker, and we all know duplicates in
btree indexes are, in a word, bad. I can imagine one or two
ridiculously bloated indexes in this scenario. It's even degenerative
in another direction - the more aggregate bloat we have, the slower
the jump from value to row locking takes, the more likely conflicts
are, the more likely bloat is.

Contrast this with my design, where re-ordering of would-be
conflicters across unique indexes (or serialization failures) can
totally nip this in the bud *if* the contention can be re-ordered
around, but if not, at least there is no need to worry about
aggregating bloat at all, because it creates no bloat.

Now, you're probably thinking "but I said I'll reverify the row for
conflicts across versions, and it'll be fine - there's generally no
need to iterate and bloat again provided no unique-indexed column
changed, even if that is more likely to occur due to the clean-up pre
row locking". Maybe I'm being unfair, but apart from requiring a
considerable amount of additional infrastructure of its own (a new
EvalPlanQual()-like thing that cares about binary equality in respect
of some columns only across row versions), I think that this is likely
to turn out to be subtly flawed in some way, simply because of the
modularity violation, so I haven't given you the benefit of the doubt
about your ability to frequently avoid repeatedly asking the index +
btree code what to do. For example, partial unique indexes - maybe
something that looked okay before because you simply didn't have cause
to insert into that unique index has to be considered in light of the
fact that it changed across row versions - are you going to stash that
knowledge too, and is it likely to affect someone who might otherwise
not have these issues really badly because we have to assume the worst
there? Do you want to do a value verification thing for that too, as
we do when deciding to insert into partial indexes in the first place?
Even if this new nothing-changed-across-versions infrastructure works,
will it work often enough in practice to be worth it -- have you ever
tracked the proportion of updates that were HOT updates in a
production DB? It isn't uncommon for it to not be great, and I think
that we can take that as a proxy for how well this will work. It could
be totally legitimate for the UPDATE portion to alter a unique indexed
column all the time.

Basically, if there's a way we can do this without changing the
on-disk format (even in a backward-compatible way), I'd be strongly
inclined to go that route unless we have a really compelling reason to
believe it's going to suck (or be outright impossible).

I don't believe that anything that I have proposed needs to break our
on-disk format - I hadn't considered what the implications might be in
this area for other proposals, but it's possible that that's an
additional advantage of doing value locking all in-memory.

[1]: /messages/by-id/CAM3SWZRV0F-DjgpXu-WxGoG9eEcLawNrEiO5+3UKRp2e5s=TSg@mail.gmail.com

[2]: /messages/by-id/CAM3SWZQUUuYYcGksVytmcGqACVMkf1ui1uvfJekM15YkWZpzhw@mail.gmail.com -- Peter Geoghegan
--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Thu, Sep 26, 2013 at 12:33 PM, Robert Haas <robertmhaas@gmail.com> wrote:

I think one thing that's pretty clear at this point is that almost any
version of this feature could be optimized for either the insert case
or the update case. For example, my proposal could be modified to
search for a conflicting tuple first, potentially wasting an index
probes (or multiple index probes, if you want to search for potential
conflicts in multiple indexes) if we're inserting, but winning heavily
in the update case.

I don't think that's really the case.

In what sense could my design really be said to prioritize either the
INSERT or the UPDATE case? I'm pretty sure that it's still necessary
to get all the value locks per unique index needed up until the first
one with a conflict even if you know that you're going to UPDATE for
*some* reason, in order for things to be well defined (which is
important, because there might be more than one conflict, and which
one is locked matters - maybe we could add DDL to let unique indexes
have a checking priority or something like that).

The only appreciable downside of my design for updates that I can
think of is that there has to be another index scan, to find the
locked-for-update row to update. However, that's probably worth it,
since it is at least relatively rare, and allows the user the
flexibility of using a more complex UPDATE predicate than "apply to
conflicter", which is something that the MySQL syntax effectively
limits users to.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Thu, Sep 26, 2013 at 11:58 PM, Peter Geoghegan <pg@heroku.com> wrote:

On Thu, Sep 26, 2013 at 12:15 PM, Robert Haas <robertmhaas@gmail.com> wrote:

Well, I think we can rule out value locks that are held for the
duration of a transaction right away. That's just not going to fly.

I think I agree with that. I don't think I remember hearing that proposed.

I think I might have been unclear - I mean locks that are held for the
duration of *another* transaction, not our own, as we wait for that
other transaction to commit/abort. I think that earlier remarks from
yourself and Andres implied that this would be necessary. Perhaps I'm
mistaken. Your most recent design proposal doesn't do this, but I
think that that's only because it restricts the user to a single
unique index - it would otherwise be necessary to sit on the earlier
value locks (index tuples belonging to an unfinished transaction)
pending the completion of some other conflicting transaction, which
has numerous disadvantages (as described in my "it suits my purposes
to have the value locks be held for only an instant" mail to you [1]).

OK, now I understand what you are saying. I don't think I agree with it.

I don't have another idea either. In fact, I'd go so far as to say
that doing any third thing that's better than those two to any
reasonable person is obviously impossible. But I'd add that we simple
cannot rollback at read committed, so we're just going to have to hold
our collective noses and do strange things with visibility.

I don't accept that as a general principal. We're writing the code;
we can make it behave any way we think best.

This is something that I haven't given remotely enough thought yet, so
please take it with a big grain of salt.

I doubt that any change to HeapTupleSatisfiesMVCC() will be
acceptable. This feature needs to restrain itself to behavior changes
that only affect users of this feature, I think.

There is certainly value in considering that, and you're right to take
that tact - it is generally valuable to have a patch be minimally
invasive. However, ultimately that's just one aspect of any given
design, an aspect that needs to be weighed against others where there
is a tension. Obviously in this instance I believe, rightly or
wrongly, that doing more - adding more infrastructure than might be
considered strictly necessary - is the least worst thing. Also,
sometimes the apparent similarity of a design to what we have today is
illusory - certainly, I think you'd at least agree that the problems
that bloating during the interim between value locking and row locking
present are qualitatively different to other problems that bloat
presents in all existing scenarios.

TBH, no, I don't think I agree with that. See further below.

Let me try and explain myself better, with reference to a concrete
example. Suppose we have a table with a primary key column, A, and a
unique constraint column, B, and we lock the pk value first and the
unique constraint value second. I'm assuming your design, but allowing
for multiple unique indexes because I don't think doing anything less
will be accepted - promise tuples have some of the same problems, as
well as some other idiosyncratic ones (see my earlier remarks on
recovery/freezing [2] for examples of those).

OK, so far I'm right with you.

So there is a fairly high probability that the pk value on A will be
unique, and a fairly low probability that the unique constraint value
on B will be unique, at least in this usage pattern of interest, where
the user is mostly going to end up updating. Mostly, we insert a
speculative regular index tuple (that points to a speculative heap
tuple that we might decide to kill) into the pk column, A, right away,
and then maybe block pending the resolution of a conflicting
transaction on the unique constraint column B. I don't think we have
any reasonable way of not blocking on A - if we go clean it up for the
wait, that's going to bloat quite dramatically, *and* we have to WAL
log. In any case you seemed to accept that cleaning up bloat
synchronously like that was just going to be too expensive. So I
suppose that rules that out. That just leaves sitting on the "value
lock" (that the pk index tuple already inserted effectively is)
indefinitely, pending the outcome of the first transaction.

Agreed.

What are the consequences of sitting on that value lock indefinitely?
Well, xacts are going to block on the pk value much more frequently,
by simple virtue of the fact that the value locks there are held for a
long time - they just needed to hear a "no" answer, which the unique
constraint was in most cases happy to immediately give, so this is
totally unnecessary. Contention is now in a certain sense almost as
bad for every unique index as it is for the weakest link. That's only
where the problems begin, though, and it isn't necessary for there to
be bad contention on more than one unique index (the pk could just be
on a serial column, say) to see bad effects.

Here's where I start to lose faith. It's unclear to me what those
other transactions are doing. If they're trying to insert a record
that conflicts with the primary key of the tuple we're inserting,
they're probably doomed, but not necessarily; we might roll back. If
they're also upserting, it's absolutely essential that they wait until
we get done before deciding what to do.

So your long-running xact that's blocking all the other sessions on
its proposed value for a (or maybe even b) - that finally gets to
proceed. Regardless of whether it commits or aborts, there will be a
big bloat race. This is because when the other sessions get the
go-ahead to proceed, they'll all run to get the row lock (one guy
might insert instead). Only one will be successful, but they'll all
kill their heap tuple on the assumption that they'll probably lock the
row, which is only true in the average case. Now, maybe you can teach
them to not bother killing the heap tuple when there are no index
tuples actually inserted to ruin things, but then maybe not, and maybe
it wouldn't help in this instance if you did teach them (because
there's a third, otherwise irrelevant constraint or whatever).

Supposing they are all upserters, it seems to me that what will
probably happen is that one of them will lock the row and update it,
and then commit. Then the next one will lock the row and update it,
and then commit. And so on. It's probably important to avoid having
them keep recreating speculative tuples and then killing them as long
as a candidate tuple is available, so that they don't create a dead
tuple per iteration. But that seems doable.

Realize you can generally only kill the heap tuple *before* you have
the row lock, because otherwise a totally innocent non-HOT update (may
not update any unique indexed columns at all) will deadlock with your
session, which I don't think is defensible, and will probably happen
often if allowed to (after all, this is upsert - users are going to
want to update their locked rows!).

I must be obtuse; I don't see why that would deadlock.

A bigger problem that I've just realized, though, is that once
somebody else has blocked on a unique index insertion, they'll be
stuck there until end of transaction even if we kill the tuple,
because they're waiting on the xid, not the index itself. That might
be fatal to my proposed design, or at least require the use of some
more clever locking regimen.

Contrast this with my design, where re-ordering of would-be
conflicters across unique indexes (or serialization failures) can
totally nip this in the bud *if* the contention can be re-ordered
around, but if not, at least there is no need to worry about
aggregating bloat at all, because it creates no bloat.

Yeah, possibly.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Sep 27, 2013 at 5:36 AM, Robert Haas <robertmhaas@gmail.com> wrote:

I don't have another idea either. In fact, I'd go so far as to say
that doing any third thing that's better than those two to any
reasonable person is obviously impossible. But I'd add that we simple
cannot rollback at read committed, so we're just going to have to hold
our collective noses and do strange things with visibility.

I don't accept that as a general principal. We're writing the code;
we can make it behave any way we think best.

I presume you're referring to the principle that we cannot throw
serialization failures at read committed. I'd suggest that letting
that happen would upset a lot of people, because it's so totally
unprecedented. A large segment of our user base would just consider
that to be Postgres randomly throwing errors, and would be totally
dismissive of the need to do so, and not without some justification -
no one else does the same. The reality is that the majority of our
users don't even know what an isolation level is. I'm not just talking
about people that use Postgres more casually, such as Heroku
customers. I've personally talked to people who didn't even know what
a transaction isolation level was, that were in a position where they
really, really should have known.

I doubt that any change to HeapTupleSatisfiesMVCC() will be
acceptable. This feature needs to restrain itself to behavior changes
that only affect users of this feature, I think.

I agree with the principle of what you're saying, but I'm not aware
that those changes to HeapTupleSatisfiesMVCC() imply any behavioral
changes for those not using the feature. Certainly, the standard
regression tests and isolation tests still pass, for what it's worth.
Having said that, I have not thought about it enough to be willing to
actually defend that bit of code. Though I must admit that I am a
little encouraged by the fact that it passes casual inspection.

I am starting to wonder if it's really necessary to have a "blessed"
update that can see the locked, not-otherwise-visible tuple. Doing
that certainly has its disadvantages, both in terms of code complexity
and in terms of being arbitrarily restrictive. We're going to have to
allow the user to see the locked row after it's updated (the new row
version that we create will naturally be visible to its creating xact)
- is it really any worse that the user can see it before an update (or
a delete)? The user could decide to effectively make the update change
nothing, and see the same thing anyway.

I get why you're averse to doing odd things to visibility - I was too.
I just don't see that we have a choice if we want this feature to work
acceptably with read committed. In addition, as it happens I just
don't see that the general situation is made any worse by the fact
that the user might be able to see the row before an update/delete.
Isn't is also weird to update or delete something you cannot see?

Couldn't EvalPlanQual() be said to be an MVCC violation on similar
grounds? It also "reaches into the future". Locking a row isn't really
that distinct from updating it in terms of the code footprint, but
also from a logical perspective.

It's probably important to avoid having
them keep recreating speculative tuples and then killing them as long
as a candidate tuple is available, so that they don't create a dead
tuple per iteration. But that seems doable.

I'm not so sure.

Realize you can generally only kill the heap tuple *before* you have
the row lock, because otherwise a totally innocent non-HOT update (may
not update any unique indexed columns at all) will deadlock with your
session, which I don't think is defensible, and will probably happen
often if allowed to (after all, this is upsert - users are going to
want to update their locked rows!).

I must be obtuse; I don't see why that would deadlock.

If you don't see it, then you aren't being obtuse in asking for
clarification. It's really easy to be wrong about this kind of thing.

If the non-HOT update updates some random row, changing the key
columns, it will lock that random row version. It will then proceed
with "value locking" (i.e. inserting index tuples in the usual way, in
this case with entirely new values). It might then block on one of the
index tuples we, the upserter, have already inserted (these are our
"value locks" under your scheme). Meanwhile, we (the upserter) might
have *already* concluded that the *old* heap row that the regular
updater is in the process of rendering invisible is to blame in
respect of some other value in some later unique index, and that *it*
must be locked. Deadlock. This seems very possible if the key values
are somewhat correlated, which is probably generally quite common.

The important observation here is that an updater, in effect, locks
both the old and new sets of values (for non-HOT updates). And as I've
already noted, any practical "value locking" implementation isn't
going to be able to prevent the update from immediately locking the
old, because that doesn't touch an index. Hence, there is an
irresolvable disconnect between value and row locking.

Are we comfortable with this? Before you answer, consider that there
was lots of bugs (their words) in the MySQL implementation of this
same basic idea surrounding excessive deadlocking - I heard through
the grapevine that they fixed a number of bugs along these lines, and
that their implementation has historically had lots of deadlocking
problems.

I think that the way to deal with weird, unprincipled deadlocking is
to simply not hold value locks at the same time as row locks - it is
my contention that the lock starvation hazards that avoiding being
smarter about this may present aren't actually an issue, unless you
have some kind of highly implausible perfect storm of read-committed
aborters inserting around the same values - only one of those needs to
commit to remedy the situation - the first "no" answer is all we need
to give up.

To repeat myself, that's really the essential nature of my design: it
is accepting of the inevitability of there being a disconnect between
value and row locking. Value locks that are implemented in a sane way
can do very little; they can only prevent a conflicting insertion from
*finishing*, and not from causing a conflict for row locking.

A bigger problem that I've just realized, though, is that once
somebody else has blocked on a unique index insertion, they'll be
stuck there until end of transaction even if we kill the tuple,
because they're waiting on the xid, not the index itself. That might
be fatal to my proposed design, or at least require the use of some
more clever locking regimen.

Well, it's really fatal to your proposed design *because* it implies
that others will be blocked on earlier value locks, which is what I
was trying to say (in saying this, I'm continuing to hold your design
to the same standard as my own, which is that it must work across
multiple unique indexes - I believe that you yourself accept this
standard based on your remarks here).

For the benefit of others who may not get what we're talking about: in
my patch, that isn't a problem, because when we block on acquiring an
xid ShareLock pending value conflict resolution, that means that the
other guy actually did insert (and did not merely think about it), and
so with that design it's entirely appropriate that we wait for his
xact to end.

Contrast this with my design, where re-ordering of would-be
conflicters across unique indexes (or serialization failures) can
totally nip this in the bud *if* the contention can be re-ordered
around, but if not, at least there is no need to worry about
aggregating bloat at all, because it creates no bloat.

Yeah, possibly.

I think that re-ordering is an important property of any design where
we cannot bail out with serialization failures. I know it seems weird,
because it seems like an MVCC violation to have our behavior altered
as a result of a transaction that committed that isn't even visible to
us. As I think you appreciate, on a certain level that's just the
nature of the beast. This might sound stupid, but: you can say the
same thing about unique constraint violations! I do not believe that
this introduces any anomalies that read committed doesn't already
permit according to the standard.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Sep 24, 2013 at 2:14 AM, Andres Freund <andres@2ndquadrant.com> wrote:

Various messages are discussing semantics around visibility. I by now
have a hard time keeping track. So let's keep the discussion of the
desired semantics to this thread.

Yes, it's pretty complicated.

I meant to comment on this here, but ended up saying some stuff to
Robert about this in the main thread, so I should probably direct you
to that. You were probably right to start a new thread, because I
think we can usefully discuss this topic in parallel, but that's just
what ended up happening.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Sep 27, 2013 at 8:36 PM, Peter Geoghegan <pg@heroku.com> wrote:

On Fri, Sep 27, 2013 at 5:36 AM, Robert Haas <robertmhaas@gmail.com> wrote:

I don't have another idea either. In fact, I'd go so far as to say
that doing any third thing that's better than those two to any
reasonable person is obviously impossible. But I'd add that we simple
cannot rollback at read committed, so we're just going to have to hold
our collective noses and do strange things with visibility.

I don't accept that as a general principal. We're writing the code;
we can make it behave any way we think best.

I presume you're referring to the principle that we cannot throw
serialization failures at read committed. I'd suggest that letting
that happen would upset a lot of people, because it's so totally
unprecedented. A large segment of our user base would just consider
that to be Postgres randomly throwing errors, and would be totally
dismissive of the need to do so, and not without some justification -
no one else does the same. The reality is that the majority of our
users don't even know what an isolation level is. I'm not just talking
about people that use Postgres more casually, such as Heroku
customers. I've personally talked to people who didn't even know what
a transaction isolation level was, that were in a position where they
really, really should have known.

Yes, it might not be a good idea. But I'm just saying, we get to decide.

I doubt that any change to HeapTupleSatisfiesMVCC() will be
acceptable. This feature needs to restrain itself to behavior changes
that only affect users of this feature, I think.

I agree with the principle of what you're saying, but I'm not aware
that those changes to HeapTupleSatisfiesMVCC() imply any behavioral
changes for those not using the feature. Certainly, the standard
regression tests and isolation tests still pass, for what it's worth.
Having said that, I have not thought about it enough to be willing to
actually defend that bit of code. Though I must admit that I am a
little encouraged by the fact that it passes casual inspection.

Well, at a minimum, it's a performance worry. Those functions are
*hot*. Single branches do matter there.

I am starting to wonder if it's really necessary to have a "blessed"
update that can see the locked, not-otherwise-visible tuple. Doing
that certainly has its disadvantages, both in terms of code complexity
and in terms of being arbitrarily restrictive. We're going to have to
allow the user to see the locked row after it's updated (the new row
version that we create will naturally be visible to its creating xact)
- is it really any worse that the user can see it before an update (or
a delete)? The user could decide to effectively make the update change
nothing, and see the same thing anyway.

If we're not going to just error out over the invisible tuple the user
needs some way to interact with it. The details are negotiable.

I get why you're averse to doing odd things to visibility - I was too.
I just don't see that we have a choice if we want this feature to work
acceptably with read committed. In addition, as it happens I just
don't see that the general situation is made any worse by the fact
that the user might be able to see the row before an update/delete.
Isn't is also weird to update or delete something you cannot see?

Couldn't EvalPlanQual() be said to be an MVCC violation on similar
grounds? It also "reaches into the future". Locking a row isn't really
that distinct from updating it in terms of the code footprint, but
also from a logical perspective.

Yes, EvalPlanQual() is definitely an MVCC violation.

Realize you can generally only kill the heap tuple *before* you have
the row lock, because otherwise a totally innocent non-HOT update (may
not update any unique indexed columns at all) will deadlock with your
session, which I don't think is defensible, and will probably happen
often if allowed to (after all, this is upsert - users are going to
want to update their locked rows!).

I must be obtuse; I don't see why that would deadlock.

If you don't see it, then you aren't being obtuse in asking for
clarification. It's really easy to be wrong about this kind of thing.

If the non-HOT update updates some random row, changing the key
columns, it will lock that random row version. It will then proceed
with "value locking" (i.e. inserting index tuples in the usual way, in
this case with entirely new values). It might then block on one of the
index tuples we, the upserter, have already inserted (these are our
"value locks" under your scheme). Meanwhile, we (the upserter) might
have *already* concluded that the *old* heap row that the regular
updater is in the process of rendering invisible is to blame in
respect of some other value in some later unique index, and that *it*
must be locked. Deadlock. This seems very possible if the key values
are somewhat correlated, which is probably generally quite common.

OK, I see.

The important observation here is that an updater, in effect, locks
both the old and new sets of values (for non-HOT updates). And as I've
already noted, any practical "value locking" implementation isn't
going to be able to prevent the update from immediately locking the
old, because that doesn't touch an index. Hence, there is an
irresolvable disconnect between value and row locking.

This part I don't follow. "locking the old"? What irresolvable
disconnect? I mean, they're different things; I get *that*.

Are we comfortable with this? Before you answer, consider that there
was lots of bugs (their words) in the MySQL implementation of this
same basic idea surrounding excessive deadlocking - I heard through
the grapevine that they fixed a number of bugs along these lines, and
that their implementation has historically had lots of deadlocking
problems.

I think that the way to deal with weird, unprincipled deadlocking is
to simply not hold value locks at the same time as row locks - it is
my contention that the lock starvation hazards that avoiding being
smarter about this may present aren't actually an issue, unless you
have some kind of highly implausible perfect storm of read-committed
aborters inserting around the same values - only one of those needs to
commit to remedy the situation - the first "no" answer is all we need
to give up.

OK, I take your point, I think. The existing system already acquires
value locks when a tuple lock is held, during an UPDATE, and we can't
change that.

Contrast this with my design, where re-ordering of would-be
conflicters across unique indexes (or serialization failures) can
totally nip this in the bud *if* the contention can be re-ordered
around, but if not, at least there is no need to worry about
aggregating bloat at all, because it creates no bloat.

Yeah, possibly.

I think that re-ordering is an important property of any design where
we cannot bail out with serialization failures. I know it seems weird,
because it seems like an MVCC violation to have our behavior altered
as a result of a transaction that committed that isn't even visible to
us. As I think you appreciate, on a certain level that's just the
nature of the beast. This might sound stupid, but: you can say the
same thing about unique constraint violations! I do not believe that
this introduces any anomalies that read committed doesn't already
permit according to the standard.

I worry about the behavior being confusing and hard to understand in
the presence of multiple unique indexes and reordering. Perhaps I
simply don't understand the problem domain well-enough yet.

From a user perspective, I would really think people would want to
specify a set of key columns and then update if a match is found on
those key columns. Suppose there's a unique index on (a, b) and
another on (c), and the user passes in (a,b,c)=(1,1,1). It's hard for
me to imagine that the user will be happy to update either (1,1,2) or
(2,2,1), whichever exists. In what situation would that be the
desired behavior?

Also, under such a programming model, if somebody drops a unique index
or adds a new one, the behavior of someone's application can
completely change. I have a hard time swallowing that. It's an
established precedent that dropping a unique index can make some other
operation fail (e.g. ADD FOREIGN KEY, and more recently CREATE VIEW ..
GROUP BY), and of course it can cause performance or plan changes.
But overturning the semantics is, I think, something new, and it
doesn't feel like a good direction.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Mon, Sep 30, 2013 at 8:32 AM, Robert Haas <robertmhaas@gmail.com> wrote:

I doubt that any change to HeapTupleSatisfiesMVCC() will be
acceptable. This feature needs to restrain itself to behavior changes
that only affect users of this feature, I think.

I agree with the principle of what you're saying, but I'm not aware
that those changes to HeapTupleSatisfiesMVCC() imply any behavioral
changes for those not using the feature.

Well, at a minimum, it's a performance worry. Those functions are
*hot*. Single branches do matter there.

Well, that certainly is a reasonable concern. Offhand, I suspect that
branch prediction helps immensely. But even if it doesn't, couldn't it
be the case that returning earlier there actually helps? Where we have
a real xid (so TransactionIdIsCurrentTransactionId() must do more than
a single test of a scalar variable), and the row is locked *only*
(which is already very cheap to check - it's another scalar variable
that we already test in a few other places in that function), isn't
there on average a high chance that the tuple ought to be visible to
our snapshot anyway?

I am starting to wonder if it's really necessary to have a "blessed"
update that can see the locked, not-otherwise-visible tuple.

If we're not going to just error out over the invisible tuple the user
needs some way to interact with it. The details are negotiable.

I think that we will error out over an invisible tuple with higher
isolation levels. Certainly, what we do there today instead of
EvalPlanQual() looping is consistent with that behavior.

Couldn't EvalPlanQual() be said to be an MVCC violation on similar
grounds? It also "reaches into the future". Locking a row isn't really
that distinct from updating it in terms of the code footprint, but
also from a logical perspective.

Yes, EvalPlanQual() is definitely an MVCC violation.

So I think that you can at least see why I'd consider that the two (my
tweaks to HeapTupleSatisfiesMVCC() and EvalPlanQual()) are isomorphic.
It just becomes the job of this new locking infrastructure to worry
about the would-be invisibility of the locked tuple, and raise a
serialization error accordingly at higher isolation levels.

The important observation here is that an updater, in effect, locks
both the old and new sets of values (for non-HOT updates). And as I've
already noted, any practical "value locking" implementation isn't
going to be able to prevent the update from immediately locking the
old, because that doesn't touch an index. Hence, there is an
irresolvable disconnect between value and row locking.

This part I don't follow. "locking the old"? What irresolvable
disconnect? I mean, they're different things; I get *that*.

Well, if you update a row, the old row version's values are locked, in
the sense that any upserter interested in inserting the same values as
the old version is going to have to block pending the outcome of the
updating xact.

The disconnect is that any attempt at a clever dance, to interplay
value and row locking such that this definitely just works first time
seems totally futile - I'm emphasizing this because it's the obvious
way to approach this basic problem. It turns out that it could only be
done at great expense, in a way that would immediately be dismissed as
totally outlandish.

OK, I take your point, I think. The existing system already acquires
value locks when a tuple lock is held, during an UPDATE, and we can't
change that.

Right.

I think that re-ordering is an important property of any design where
we cannot bail out with serialization failures.

I worry about the behavior being confusing and hard to understand in
the presence of multiple unique indexes and reordering. Perhaps I
simply don't understand the problem domain well-enough yet.

It's only confusing if you are worried about what concurrent sessions
do with respect to each other at this low level. In which case, just
use a higher isolation level and pay the price. I'm not introducing
any additional anomalies described and prohibited by the standard by
doing this, and indeed the order of retrying in the event of a
conflict today is totally undefined, so this line of thinking is not
inconsistent with how things work today. Today, strictly speaking some
unique constraint violations might be more appropriate as
serialization failures. So with this new functionality, when used,
they're going to be actual serialization failures where that's
appropriate, where we'd otherwise go do something else other than
error. Why burden read committed like that? (Actually, fwiw I suspect
that currently the SSI guarantees *can* be violated with unique retry
re-ordering, but that's a whole other story, and is pretty subtle).

Let me come right out and say it: Yes, part of the reason that I'm
taking this line is because it's convenient to my implementation from
a number of different perspectives. But one of those perspectives is
that it will help performance in the face of contention immensely,
without violating any actual precept held today (by us or by the
standard or by anyone else AFAIK), and besides, my basic design is
informed by sincerely-held beliefs about what will actually work
within the constraints presented.

From a user perspective, I would really think people would want to
specify a set of key columns and then update if a match is found on
those key columns. Suppose there's a unique index on (a, b) and
another on (c), and the user passes in (a,b,c)=(1,1,1). It's hard for
me to imagine that the user will be happy to update either (1,1,2) or
(2,2,1), whichever exists. In what situation would that be the
desired behavior?

You're right - that isn't desirable. The reason that we go to all this
trouble with locking multiple values concurrently boils down to
preventing the user from having to specify a constraint name - it's
usually really obvious *to users* that understand their schema, so why
bother them with that esoteric detail? The user *is* more or less
required to have a particular constraint in mind when writing their
DML (for upsert). It could be that that constraint has a 1:1
correlation with another constraint in practice, which would also work
out fine - they'd specify one or the other constrained column (maybe
both) in the subsequent update's predicate. But generally, yes,
they're out of luck here, until we get around to implementing MERGE in
its full generality, which I think what I've proposed is a logical
stepping stone towards (again, because it involves locking values
across unique indexes simultaneously).

Now, at least what I've proposed has the advantage of allowing the
user to add some controls in their update's predicate. So if they only
had updating (1,1,2) in mind, they could put WHERE a = 1 AND b = 1 in
there too (I'm imagining the wCTE pattern is used). They'd then be
able to inspect the value of the FOUND pseudo-variable or whatever.
Now, I'm assuming that we'd somehow be able to tell that the insert
hasn't succeeded (i.e. it locked), and maybe that doesn't accord very
well with these kinds of facilities as they exist today, but it
doesn't seem like too much extra work (MySQL would consider that both
the locked and updated rows were affected, which might help us here).

MySQL's INSERT...ON DUPLICATE KEY UPDATE has nothing like this - there
is no guidance as to why you went to update, and you cannot have a
separate update qual. Users better just get it right!

Maybe what's really needed here is INSERT...ON DUPLICATE KEY LOCK FOR
UPDATE RETURNING LOCKED... . You can see what was actually locked, and
act on *that* as appropriate. Though you don't get to see the actual
value of default expressions and so on, which is a notable
disadvantage over RETURNING REJECTS... .

The advantage of RETURNING LOCKED would be you could check if it
LOCKED for the reason you thought it should have. If it didn't, then
surely what you'd prefer would be a unique constraint violation, so
you can just go throw an error in application code (or maybe consider
another value for the columns that surprised you).

What do others think?

Also, under such a programming model, if somebody drops a unique index
or adds a new one, the behavior of someone's application can
completely change. I have a hard time swallowing that. It's an
established precedent that dropping a unique index can make some other
operation fail (e.g. ADD FOREIGN KEY, and more recently CREATE VIEW ..
GROUP BY), and of course it can cause performance or plan changes.
But overturning the semantics is, I think, something new, and it
doesn't feel like a good direction.

In what sense is causing, or preventing an error (the current state of
affairs) not a behavioral change? I'd have thought it a very
significant one. If what you're saying here is true, wouldn't that
mandate that we specify the name of a unique index inline, within DML?
I thought we were in agreement that that wasn't desirable.

If you think it's a bit odd that we lock every value while the user
essentially has one constraint in mind when writing their DML,
consider:

1) We need this for MERGE anyway.

2) Don't underestimate the intellectual overhead for developers and
operations personnel of adding an application-defined significance to
unique indexes that they don't otherwise have. It sure would suck if a
refactoring effort to normalize unique index naming style had the
effect of breaking a slew of application code. Certainly, everyone
else seems to have reached the same conclusion in their own
implementation of upsert, because they don't require that a unique
index be specified, even when that could have unexpected results.

3) The problems that getting the details wrong present can be
ameliorated by developers who feel it might be a problem for them, as
already described. I think in the vast majority of cases it just
obviously won't be a problem to begin with.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Mon, Sep 30, 2013 at 3:45 PM, Peter Geoghegan <pg@heroku.com> wrote:

If you think it's a bit odd that we lock every value while the user
essentially has one constraint in mind when writing their DML,
consider:

I should add to that list:

4) Locking all the values at once is necessary for the behavior of the
locking to be well-defined -- I feel we need to know that some exact
tuple is to blame (according to our well defined ordering for checking
unique indexes for conflicts) for at least one instant in time.

Given that we need to be the first to change the row without anything
being altered to it, this ought to be sufficient. If you think it's
bad that some other session can come in and insert a tuple that would
have caused us to decide differently (before *our* transaction commits
but *after* we've inserted), now you're into blaming the *wrong* tuple
in the future, and I can't get excited about that - we always prefer a
tuple normally visible to our snapshot, but if forced to (if there is
none) we just throw a serialization failure (where appropriate). So
for read committed you can have no *principled* beef with this, but
for serializable you're going to naturally prefer the
currently-visible tuple generally (that's the only correct behavior
there that won't error - there *better* be something visible).

Besides, the way the user tacitly has to use the feature with one
particular constraint in mind kind of implies that this cannot
happen...

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Mon, Sep 30, 2013 at 9:11 PM, Peter Geoghegan <pg@heroku.com> wrote:

On Mon, Sep 30, 2013 at 3:45 PM, Peter Geoghegan <pg@heroku.com> wrote:

If you think it's a bit odd that we lock every value while the user
essentially has one constraint in mind when writing their DML,
consider:

I should add to that list:

4) Locking all the values at once is necessary for the behavior of the
locking to be well-defined -- I feel we need to know that some exact
tuple is to blame (according to our well defined ordering for checking
unique indexes for conflicts) for at least one instant in time.

Given that we need to be the first to change the row without anything
being altered to it, this ought to be sufficient. If you think it's
bad that some other session can come in and insert a tuple that would
have caused us to decide differently (before *our* transaction commits
but *after* we've inserted), now you're into blaming the *wrong* tuple
in the future, and I can't get excited about that - we always prefer a
tuple normally visible to our snapshot, but if forced to (if there is
none) we just throw a serialization failure (where appropriate). So
for read committed you can have no *principled* beef with this, but
for serializable you're going to naturally prefer the
currently-visible tuple generally (that's the only correct behavior
there that won't error - there *better* be something visible).

Besides, the way the user tacitly has to use the feature with one
particular constraint in mind kind of implies that this cannot
happen...

This patch is still marked as "Needs Review" in the CommitFest
application. There's no reviewer, but in fact Andres and I both spent
quite a lot of time providing design feedback (probably more than I
spent on any other CommitFest patch). I think it's clear that the
patch as submitted is not committable, so as far as the CommitFest
goes I'm going to mark it Returned with Feedback.

I think there are still some design considerations to work out here,
but honestly I'm not totally sure what the remaining points of
disagreement are. It would be nice to here the opinions of a few more
people on the concurrency issues, but beyond that I think that a lot
of this is going to boil down to whether the details of the value
locking can be made to seem palatable enough and sufficiently
low-overhead in the common case. I don't believe we can comment on
that in the abstract.

There's still some question in my mind as to what the semantics ought
to be. I do understand Peter's point that having to specify a
particular index would be grotty, but I'm not sure it invalidates my
point that having to work across multiple indexes could lead to
surprising results in some scenarios. I'm not going to stand here and
hold my breath, though: if that's the only thing that makes me nervous
about the final patch, I'll not object to it on that basis.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Oct 9, 2013 at 11:24 AM, Robert Haas <robertmhaas@gmail.com> wrote:

This patch is still marked as "Needs Review" in the CommitFest
application. There's no reviewer, but in fact Andres and I both spent
quite a lot of time providing design feedback (probably more than I
spent on any other CommitFest patch).

Right, thank you both.

I think there are still some design considerations to work out here,
but honestly I'm not totally sure what the remaining points of
disagreement are. It would be nice to here the opinions of a few more
people on the concurrency issues, but beyond that I think that a lot
of this is going to boil down to whether the details of the value
locking can be made to seem palatable enough and sufficiently
low-overhead in the common case. I don't believe we can comment on
that in the abstract.

I agree that we cannot comment on it in the abstract. I am optimistic
that we can make the value locking work better without regressing the
common cases (especially if we're only concerned about not regressing
users that never use the feature, as opposed to having some
expectation for regular inserters inserting values into the same
ranges as an upserter). That's not my immediate concern, though - my
immediate concern is getting the concurrency and visibility issues
scrutinized.

What would it take to get the patch into a committable state if the
value locking had essentially the same properties (they were held
instantaneously), but were perfect? There is no point in giving the
value locking implementation too much further consideration unless
that question can be answered. In the past I've said that row locking
and value locking cannot be considered separately, but that was when
it was generally assumed that value locks had to persist for a long
time in a way that I don't think is feasible (and I think Robert would
now agree that it's at the very least very hard). Persisting value
locks basically make not regressing the general case hard, when you
think about the implementation. As Robert remarked, regular btree
index insertion blockings on an xid, not a value, and cannot be easily
made to appreciate that the "value lock" that a would-be duplicate
index tuple represents may just be held for a short time, and not the
entire duration of their inserter's transaction.

There's still some question in my mind as to what the semantics ought
to be. I do understand Peter's point that having to specify a
particular index would be grotty, but I'm not sure it invalidates my
point that having to work across multiple indexes could lead to
surprising results in some scenarios. I'm not going to stand here and
hold my breath, though: if that's the only thing that makes me nervous
about the final patch, I'll not object to it on that basis.

I should be so lucky! :-)

Unfortunately, I have a very busy schedule in the month ahead,
including travelling to Ireland and Japan, so I don't think I'm going
to get the opportunity to work on this too much. I'll try and produce
a V4 that formally proposes some variant of my ideas around visibility
of locked tuples.

Here are some things you might not like about this patch, if we're
still assuming that the value locks are prototype and it's useful to
defer discussion around their implementation:

* The lock starvation hazards around going from value locking to row
locking, and retrying if it doesn't work out (i.e. if the row and its
descendant rows cannot be locked without what would ordinarily
necessitate using EvalPlanQual()). I don't see what we could do about
those, other than checking for changes in the rows unique index
values, which would be complex. I understand the temptation to do
that, but the fact is that that isn't going to work all the time -
some unique index value may well change every time. By doing that
you've already accepted whatever hazard may exist, and it becomes a
question of degree. Which is fine, but I don't see that the current
degree is actually much of problem in the real world.

* Reordering of value locks generally. I still need to ensure this
will behave reasonably at higher isolation levels (i.e. they'll get a
serialization failure). I think that Robert accepts that this isn't
inconsistent with read committed's documented behavior, and that it is
useful, and maybe even essential.

* The basic question of whether or not it's possible to lock values
and rows at the same time, and if that matters (because it turns out
what looks like that isn't, because deleters will effectively lock
values without even touching an index). I think Robert saw the
difficulty of doing this, but it would be nice to get a definitive
answer. I think that any MERGE implementation worth its salt will not
deadlock without the potential for multiple rows to be locked in an
inconsistent order, so this shouldn't either, and as I believe I
demonstrated, value locks and row locks should not be held at the same
time for at least that reason. Right?

* The syntax. I like the composability, and the way it's likely to
become idiomatic to combine it with wCTEs. Others may not.

* The visibility hacks that V4 is likely to have. The fact that
preserving the composable syntax may imply changes to
HeapTupleSatisfiesMVCC() so that rows locked but with no currently
visible version (under conventional rules) are visible to our snapshot
by virtue of having been locked all the same (this only matters at
read committed).

So I think that what this patch really could benefit from is lots of
scrutiny around the concurrency issues. It would be unfair to ask for
that before at least producing a V4, so I'll clean up what I already
have and post it, probably on Sunday.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Oct 9, 2013 at 4:11 PM, Peter Geoghegan <pg@heroku.com> wrote:

* The lock starvation hazards around going from value locking to row
locking, and retrying if it doesn't work out (i.e. if the row and its
descendant rows cannot be locked without what would ordinarily
necessitate using EvalPlanQual()). I don't see what we could do about
those, other than checking for changes in the rows unique index
values, which would be complex. I understand the temptation to do
that, but the fact is that that isn't going to work all the time -
some unique index value may well change every time. By doing that
you've already accepted whatever hazard may exist, and it becomes a
question of degree. Which is fine, but I don't see that the current
degree is actually much of problem in the real world.

Some of the decisions we make here may end up being based on measured
performance rather than theoretical analysis.

* Reordering of value locks generally. I still need to ensure this
will behave reasonably at higher isolation levels (i.e. they'll get a
serialization failure). I think that Robert accepts that this isn't
inconsistent with read committed's documented behavior, and that it is
useful, and maybe even essential.

I think there's a sentence missing here, or something. Obviously, the
behavior at higher isolation levels is neither consistent nor
inconsistent with read committed's documented behavior; it's another
issue entirely.

* The basic question of whether or not it's possible to lock values
and rows at the same time, and if that matters (because it turns out
what looks like that isn't, because deleters will effectively lock
values without even touching an index). I think Robert saw the
difficulty of doing this, but it would be nice to get a definitive
answer. I think that any MERGE implementation worth its salt will not
deadlock without the potential for multiple rows to be locked in an
inconsistent order, so this shouldn't either, and as I believe I
demonstrated, value locks and row locks should not be held at the same
time for at least that reason. Right?

Right.

* The syntax. I like the composability, and the way it's likely to
become idiomatic to combine it with wCTEs. Others may not.

I've actually lost track of what syntax you're proposing.

* The visibility hacks that V4 is likely to have. The fact that
preserving the composable syntax may imply changes to
HeapTupleSatisfiesMVCC() so that rows locked but with no currently
visible version (under conventional rules) are visible to our snapshot
by virtue of having been locked all the same (this only matters at
read committed).

I continue to think this is a bad idea.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Oct 9, 2013 at 5:37 PM, Robert Haas <robertmhaas@gmail.com> wrote:

* Reordering of value locks generally. I still need to ensure this
will behave reasonably at higher isolation levels (i.e. they'll get a
serialization failure). I think that Robert accepts that this isn't
inconsistent with read committed's documented behavior, and that it is
useful, and maybe even essential.

I think there's a sentence missing here, or something. Obviously, the
behavior at higher isolation levels is neither consistent nor
inconsistent with read committed's documented behavior; it's another
issue entirely.

Here, "this" referred to the reordering concept generally. So I was
just saying that I'm not actually introducing any anomaly that is
described by the standard at read committed, and that at repeatable
read+, we can have actual serial ordering of value locks without
requiring them to last a long time, because we can throw serialization
failures, and can even do so when not strictly logically necessary.

* The basic question of whether or not it's possible to lock values
and rows at the same time, and if that matters (because it turns out
what looks like that isn't, because deleters will effectively lock
values without even touching an index). I think Robert saw the
difficulty of doing this, but it would be nice to get a definitive
answer. I think that any MERGE implementation worth its salt will not
deadlock without the potential for multiple rows to be locked in an
inconsistent order, so this shouldn't either, and as I believe I
demonstrated, value locks and row locks should not be held at the same
time for at least that reason. Right?

Right.

I'm glad we're on the same page with that - it's a very important
consideration to my mind.

* The syntax. I like the composability, and the way it's likely to
become idiomatic to combine it with wCTEs. Others may not.

I've actually lost track of what syntax you're proposing.

I'm continuing to propose:

INSERT...ON DUPLICATE KEY LOCK FOR UPDATE

with a much less interesting variant that could be jettisoned:

INSERT...ON DUPLICATE KEY IGNORE

I'm also proposing extended RETURNING to make it work with this. So
the basic idea is that within Postgres, the idiomatic way to correctly
do upsert becomes something like:

postgres=# with r as (
insert into foo(a,b)
values (5, '!'), (6, '@')
on duplicate key lock for update
returning rejects *
)
update foo set b = r.b from r where foo.a = r.a;

* The visibility hacks that V4 is likely to have. The fact that
preserving the composable syntax may imply changes to
HeapTupleSatisfiesMVCC() so that rows locked but with no currently
visible version (under conventional rules) are visible to our snapshot
by virtue of having been locked all the same (this only matters at
read committed).

I continue to think this is a bad idea.

Fair enough.

Is it just because of performance concerns? If so, that's probably not
that hard to address. It either has a measurable impact on performance
for a very unsympathetic benchmark or it doesn't. I guess that's the
standard that I'll be held to, which is probably fair.

Do you see the appeal of the composable syntax?

I appreciate that it's odd that serializable transactions now have to
worry about seeing something they shouldn't have seen (when they
conclusively have to go lock a row version not current to their
snapshot). But that's simpler than any of the alternatives that I see.
Does there really need to be a new snapshot type with one tiny
difference that apparently doesn't actually affect conventional
clients of MVCC snapshots?

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Oct 9, 2013 at 9:30 PM, Peter Geoghegan <pg@heroku.com> wrote:

* The syntax. I like the composability, and the way it's likely to
become idiomatic to combine it with wCTEs. Others may not.

I've actually lost track of what syntax you're proposing.

I'm continuing to propose:

INSERT...ON DUPLICATE KEY LOCK FOR UPDATE

with a much less interesting variant that could be jettisoned:

INSERT...ON DUPLICATE KEY IGNORE

I'm also proposing extended RETURNING to make it work with this. So
the basic idea is that within Postgres, the idiomatic way to correctly
do upsert becomes something like:

postgres=# with r as (
insert into foo(a,b)
values (5, '!'), (6, '@')
on duplicate key lock for update
returning rejects *
)
update foo set b = r.b from r where foo.a = r.a;

I can't claim to be enamored of this syntax.

* The visibility hacks that V4 is likely to have. The fact that
preserving the composable syntax may imply changes to
HeapTupleSatisfiesMVCC() so that rows locked but with no currently
visible version (under conventional rules) are visible to our snapshot
by virtue of having been locked all the same (this only matters at
read committed).

I continue to think this is a bad idea.

Fair enough.

Is it just because of performance concerns? If so, that's probably not
that hard to address. It either has a measurable impact on performance
for a very unsympathetic benchmark or it doesn't. I guess that's the
standard that I'll be held to, which is probably fair.

That's part of it; but I also think that HeapTupleSatisfiesMVCC() is a
pretty fundamental bit of the system that I am loathe to tamper with.
We can try to talk ourselves into believing that the definition change
will only affect this case, but I'm wary that there will be
unanticipated consequences, or simply that we'll find, after it's far
too late to do anything about it, that we don't particularly care for
the new semantics. It's probably an overstatement to say that I'll
oppose any whatsoever that touches the semantics of that function, but
not by much.

Do you see the appeal of the composable syntax?

To some extent. It seems to me that what we're designing is a giant
grotty hack, albeit a convenient one. But if we're not really going
to get MERGE, I'm not sure how much good it is to try to pretend we've
got something general.

I appreciate that it's odd that serializable transactions now have to
worry about seeing something they shouldn't have seen (when they
conclusively have to go lock a row version not current to their
snapshot).

Surely that's never going to be acceptable. At read committed,
locking a version not current to the snapshot might be acceptable if
we hold our nose, but at any higher level I think we have to fail with
a serialization complaint.

But that's simpler than any of the alternatives that I see.
Does there really need to be a new snapshot type with one tiny
difference that apparently doesn't actually affect conventional
clients of MVCC snapshots?

I think that's the wrong way of thinking about it. If you're
introducing a new type of snapshot, or tinkering with the semantics of
an existing one, I think that's a reason to reject the patch straight
off. We should be looking for a design that doesn't require that. If
we can't find one, I'm not sure we should do this at all.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2013-10-11 08:43:43 -0400, Robert Haas wrote:

I appreciate that it's odd that serializable transactions now have to
worry about seeing something they shouldn't have seen (when they
conclusively have to go lock a row version not current to their
snapshot).

Surely that's never going to be acceptable. At read committed,
locking a version not current to the snapshot might be acceptable if
we hold our nose, but at any higher level I think we have to fail with
a serialization complaint.

I think an UPSERTish action in RR/SERIALIZABLE that notices a concurrent
update should and has to *ALWAYS* raise a serialization
failure. Anything else will cause violations of the given guarantees.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Oct 11, 2013 at 10:02 AM, Andres Freund <andres@2ndquadrant.com> wrote:

On 2013-10-11 08:43:43 -0400, Robert Haas wrote:

I appreciate that it's odd that serializable transactions now have to
worry about seeing something they shouldn't have seen (when they
conclusively have to go lock a row version not current to their
snapshot).

Surely that's never going to be acceptable. At read committed,
locking a version not current to the snapshot might be acceptable if
we hold our nose, but at any higher level I think we have to fail with
a serialization complaint.

I think an UPSERTish action in RR/SERIALIZABLE that notices a concurrent
update should and has to *ALWAYS* raise a serialization
failure. Anything else will cause violations of the given guarantees.

Sorry, this was just a poor choice of words on my part. I totally
agree with you here. Although I wasn't even talking about noticing a
concurrent update - I was talking about noticing that a tuple that
it's necessary to lock isn't visible to a serializable snapshot in the
first place (which should also fail).

What I actually meant was that it's odd that that one case (reason for
returning) added to HeapTupleSatisfiesMVCC() will always obligate
Serializable transactions to throw a serialization failure. Though
that isn't strictly true; the modifications to
HeapTupleSatisfiesMVCC() that I'm likely to propose also redundantly
work for other cases where, if I'm not mistaken, that's okay (today,
if you've exclusively locked a tuple and it hasn't been
updated/deleted, why shouldn't it be visible to your snapshot?). The
onus is on the executor-level code to notice this
should-be-invisibility for non-read-committed, probably immediately
after returning from value locking.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Oct 11, 2013 at 5:43 AM, Robert Haas <robertmhaas@gmail.com> wrote:

* The visibility hacks that V4 is likely to have. The fact that
preserving the composable syntax may imply changes to
HeapTupleSatisfiesMVCC() so that rows locked but with no currently
visible version (under conventional rules) are visible to our snapshot
by virtue of having been locked all the same (this only matters at
read committed).

I continue to think this is a bad idea.

Is it just because of performance concerns? /

That's part of it; but I also think that HeapTupleSatisfiesMVCC() is a
pretty fundamental bit of the system that I am loathe to tamper with.
We can try to talk ourselves into believing that the definition change
will only affect this case, but I'm wary that there will be
unanticipated consequences, or simply that we'll find, after it's far
too late to do anything about it, that we don't particularly care for
the new semantics. It's probably an overstatement to say that I'll
oppose any whatsoever that touches the semantics of that function, but
not by much.

A tuple that is exclusively locked by our transaction and not updated
or deleted being visible on that basis alone isn't *that* hard to
reason about. Granted, we need to be very careful here, but we're
talking about 3 lines of code.

Do you see the appeal of the composable syntax?

To some extent. It seems to me that what we're designing is a giant
grotty hack, albeit a convenient one. But if we're not really going
to get MERGE, I'm not sure how much good it is to try to pretend we've
got something general.

Well, to be fair perhaps all of the things that you consider grotty
hacks seem like inherent requirements to me, for any half-way
reasonable upsert implementation on any system, that has the essential
property of upsert: an atomic insert-or-update (or maybe serialization
failure).

But that's simpler than any of the alternatives that I see.
Does there really need to be a new snapshot type with one tiny
difference that apparently doesn't actually affect conventional
clients of MVCC snapshots?

I think that's the wrong way of thinking about it. If you're
introducing a new type of snapshot, or tinkering with the semantics of
an existing one, I think that's a reason to reject the patch straight
off. We should be looking for a design that doesn't require that. If
we can't find one, I'm not sure we should do this at all.

I'm confused by this. We need to lock a row not visible to our
snapshot under conventional rules. I think we can rule out
serialization failures at read committed. That just leaves changing
something about the visibility rules of an existing snapshot type, or
creating a new snapshot type, no?

It would also be unacceptable to update a tuple, and not have the new
row version (which of course will still have "information from the
future") visible to our snapshot - what would regular RETURNING
return? So what do you have in mind? I don't think that locking a row
and updating it are really that distinct anyway. The benefit of
locking is that we don't have to update. We can delete, for example.

Perhaps I've totally missed your point here, but to me it sounds like
you're saying that certain properties must always be preserved that
are fundamentally in tension with upsert working in the way people
expect, and the way it is bound to actually work in numerous other
systems.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Oct 9, 2013 at 1:11 PM, Peter Geoghegan <pg@heroku.com> wrote:

Unfortunately, I have a very busy schedule in the month ahead,
including travelling to Ireland and Japan, so I don't think I'm going
to get the opportunity to work on this too much. I'll try and produce
a V4 that formally proposes some variant of my ideas around visibility
of locked tuples.

V4 is attached.

Most notably, this adds the modifications to HeapTupleSatisfiesMVCC(),
though they're neater than in the snippet I sent earlier.

There is also some clean-up around row-level locking. That code has
been simplified. I also try and handle serialization failures in a
better way, though that really needs the attention of a subject matter
expert.

There are a few additional XXX comments highlighting areas of concern,
particularly around serializable behavior. I've deferred making higher
isolation levels care about wrongfully relying on the special
HeapTupleSatisfiesMVCC() exception (e.g. they won't throw a
serialization failure, mostly because I couldn't decide on where to do
the test on time prior to travelling tomorrow).

I've added code to do heap_prepare_insert before value locks are held.
Whatever our eventual value locking implementation, that's going to be
a useful optimization. Though unfortunately I ran out of time to give
this the scrutiny it really deserves, I suppose that it's something
that we can return to later.

I ask that reviewers continue to focus on concurrency issues and broad
design issues, and continue to defer discussion about an eventual
value locking implementation. I continue to think that that's the most
useful way of proceeding for the time being. My earlier points about
probable areas of concern [1]/messages/by-id/CAM3SWZSvSrTzPhjNPjahtJ0rFfS-gJFhU86Vpewf+eO8GwZXNQ@mail.gmail.com remain a good place for reviewers to
start.

[1]: /messages/by-id/CAM3SWZSvSrTzPhjNPjahtJ0rFfS-gJFhU86Vpewf+eO8GwZXNQ@mail.gmail.com

--
Peter Geoghegan

On Fri, Oct 11, 2013 at 2:30 PM, Peter Geoghegan <pg@heroku.com> wrote:

But that's simpler than any of the alternatives that I see.
Does there really need to be a new snapshot type with one tiny
difference that apparently doesn't actually affect conventional
clients of MVCC snapshots?

I think that's the wrong way of thinking about it. If you're
introducing a new type of snapshot, or tinkering with the semantics of
an existing one, I think that's a reason to reject the patch straight
off. We should be looking for a design that doesn't require that. If
we can't find one, I'm not sure we should do this at all.

I'm confused by this. We need to lock a row not visible to our
snapshot under conventional rules. I think we can rule out
serialization failures at read committed. That just leaves changing
something about the visibility rules of an existing snapshot type, or
creating a new snapshot type, no?

It would also be unacceptable to update a tuple, and not have the new
row version (which of course will still have "information from the
future") visible to our snapshot - what would regular RETURNING
return? So what do you have in mind? I don't think that locking a row
and updating it are really that distinct anyway. The benefit of
locking is that we don't have to update. We can delete, for example.

Well, the SQL standard way of doing this type of operation is MERGE.
The alternative we know exists in other databases is REPLACE; there's
also INSERT .. ON DUPLICATE KEY update. In all of those cases,
whatever weirdness exists around MVCC is confined to that one command.
I tend to think we should do similarly, with the goal that
HeapTupleSatisfiesMVCC need not change at all.

I don't have the only vote here, of course, but my feeling is that
that's more likely to be a good route.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Oct 15, 2013 at 5:15 AM, Robert Haas <robertmhaas@gmail.com> wrote:

Well, the SQL standard way of doing this type of operation is MERGE.
The alternative we know exists in other databases is REPLACE; there's
also INSERT .. ON DUPLICATE KEY update. In all of those cases,
whatever weirdness exists around MVCC is confined to that one command.
I tend to think we should do similarly, with the goal that
HeapTupleSatisfiesMVCC need not change at all.

I don't think that it's very pragmatic to define success in terms of
not modifying a single visibility function. I feel it would be more
useful to define it as providing acceptable, non-surprising semantics,
while not regressing performance in other areas.

The fact remains that you're going to have a create a new snapshot
type even for this special case, so I don't see any win as regards
managing invasiveness here. Quite the contrary, in fact.

I don't have the only vote here, of course, but my feeling is that
that's more likely to be a good route.

Naturally we all want MERGE. It seems self-defeating to insist on
something significantly harder that there is significant less demand
for, though. I thought that there was at least informal agreement that
this sort of approach was preferable to MERGE in its full generality,
based on feedback at the 2012 developer meeting. I really don't think
that what I've done here is any worse than INSERT...ON DUPLICATE KEY
UPDATE in any of the areas you express concern about here. REPLACE has
some serious problems, and I just don't see it as a viable alternative
at all - just ask any MySQL user.

MERGE is of course more flexible to what I have here in some ways, but
actually less flexible in other ways. I think that the real point of
MERGE is that it's defined in a way that serves data warehousing use
cases very well: the semantics constrain things such that the executor
only has to execute a single ModifyTable node that does inserts,
updates and deletes in a single scan. That's great, but what if it's
useful to do that CRUD (yes, this can include selects) to entirely
different tables? Or what if the relevant DML will only come in a
later statement in the same transaction?

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Oct 15, 2013 at 8:07 AM, Peter Geoghegan <pg@heroku.com> wrote:

Naturally we all want MERGE. It seems self-defeating to insist on
something significantly harder that there is significant less demand
for, though.

I hasten to add: which is not to imply that you're insisting rather
than expressing a sentiment.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Oct 15, 2013 at 11:07 AM, Peter Geoghegan <pg@heroku.com> wrote:

On Tue, Oct 15, 2013 at 5:15 AM, Robert Haas <robertmhaas@gmail.com> wrote:

Well, the SQL standard way of doing this type of operation is MERGE.
The alternative we know exists in other databases is REPLACE; there's
also INSERT .. ON DUPLICATE KEY update. In all of those cases,
whatever weirdness exists around MVCC is confined to that one command.
I tend to think we should do similarly, with the goal that
HeapTupleSatisfiesMVCC need not change at all.

I don't think that it's very pragmatic to define success in terms of
not modifying a single visibility function. I feel it would be more
useful to define it as providing acceptable, non-surprising semantics,
while not regressing performance in other areas.

The fact remains that you're going to have a create a new snapshot
type even for this special case, so I don't see any win as regards
managing invasiveness here. Quite the contrary, in fact.

Well, we might have to agree to disagree.

I don't have the only vote here, of course, but my feeling is that
that's more likely to be a good route.

Naturally we all want MERGE. It seems self-defeating to insist on
something significantly harder that there is significant less demand
for, though. I thought that there was at least informal agreement that
this sort of approach was preferable to MERGE in its full generality,
based on feedback at the 2012 developer meeting. I really don't think
that what I've done here is any worse than INSERT...ON DUPLICATE KEY
UPDATE in any of the areas you express concern about here. REPLACE has
some serious problems, and I just don't see it as a viable alternative
at all - just ask any MySQL user.

MERGE is of course more flexible to what I have here in some ways, but
actually less flexible in other ways. I think that the real point of
MERGE is that it's defined in a way that serves data warehousing use
cases very well: the semantics constrain things such that the executor
only has to execute a single ModifyTable node that does inserts,
updates and deletes in a single scan. That's great, but what if it's
useful to do that CRUD (yes, this can include selects) to entirely
different tables? Or what if the relevant DML will only come in a
later statement in the same transaction?

I'm not saying "go implement MERGE". I'm saying, make the
insert-or-update operation a single statement, using some syntax TBD,
instead of requiring the use of a new insert statement that makes
invisible rows visible as a side effect, so that you can wrap that in
a CTE and feed it to an update statement. That's complex and, AFAICS,
unlike how any other database product handles this.

Again, other people can have different opinions on this, and that's
fine. I'm just giving you mine.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2013-10-15 11:11:24 -0400, Robert Haas wrote:

I'm not saying "go implement MERGE". I'm saying, make the
insert-or-update operation a single statement, using some syntax TBD,
instead of requiring the use of a new insert statement that makes
invisible rows visible as a side effect, so that you can wrap that in
a CTE and feed it to an update statement. That's complex and, AFAICS,
unlike how any other database product handles this.

I think we most definitely should provide a single statement
variant. That's the one users yearn for.

I also would like a variant where I can lock a row on conflict, for
multimaster scenarios, but that doesn't necessarily have to be exposed
to SQL.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Oct 15, 2013 at 8:11 AM, Robert Haas <robertmhaas@gmail.com> wrote:

I'm not saying "go implement MERGE". I'm saying, make the
insert-or-update operation a single statement, using some syntax TBD,
instead of requiring the use of a new insert statement that makes
invisible rows visible as a side effect, so that you can wrap that in
a CTE and feed it to an update statement. That's complex and, AFAICS,
unlike how any other database product handles this.

Well, lots of other databases have their own unique way of doing this
- apart from MySQL's INSERT...ON DUPLICATE KEY UPDATE, there is a
variant within Teradata, Sybase and SQLite. They're all different. And
in the case of Teradata, it was an interim feature towards MERGE which
came in a much later release, which is how I see this.

No other database system even has writeable CTEs, of course. It's a
fairly recent idea.

Again, other people can have different opinions on this, and that's
fine. I'm just giving you mine.

I will defer to the majority opinion here. But you also expressed
concern about surprising results due to the wrong unique constraint
violation being the source of a conflict. Couldn't this syntax (with
the wCTE upsert pattern) help with that, by naming the constant
inserted in the update too? It would be pretty simple to expose that,
and far less grotty than naming a unique index in DML.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Oct 15, 2013 at 11:34 AM, Peter Geoghegan <pg@heroku.com> wrote:

Again, other people can have different opinions on this, and that's
fine. I'm just giving you mine.

I will defer to the majority opinion here. But you also expressed
concern about surprising results due to the wrong unique constraint
violation being the source of a conflict. Couldn't this syntax (with
the wCTE upsert pattern) help with that, by naming the constant
inserted in the update too? It would be pretty simple to expose that,
and far less grotty than naming a unique index in DML.

Well, I don't know that any of us can claim to have a lock on what the
syntax should look like. I think we need to hear some proposals.
You've heard my gripe about the current syntax (which Andres appears
to share), but I shan't attempt to prejudice you in favor of my
preferred alternative, because I don't have one yet. There could be
other ways of avoiding that problem, though. Here's an example:

UPSERT table (keycol1, ..., keycoln) = (keyval1, ..., keyvaln) SET
(nonkeycol1, ..., nonkeycoln) = (nonkeyval1, ..., nonkeyvaln)

That's pretty ugly on multiple levels, and I'm definitely not
proposing that exact thing, but the idea is: look for a record that
matches on the key columns/values; if found, update the non-key
columns with the corresponding values; if not found, construct a new
row with both the key and nonkey column sets and insert it. If no
matching unique index exists we'll have to fail, but we stop short of
having to mention the name of that index.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Oct 15, 2013 at 9:56 AM, Robert Haas <robertmhaas@gmail.com> wrote:

Well, I don't know that any of us can claim to have a lock on what the
syntax should look like.

Sure. But it's not just syntax. We're talking about functional
differences too, since you're talking about mandating an update, which
is a not the same as an "update locked row only conditionally", or a
delete.

I get that it's a little verbose, but then this is ORM plumbing for
many of those that would prefer a more succinct syntax. Those people
would also benefit from having their ORM do something much more
powerful for them when needed.

I think we need to hear some proposals.

Agreed.

You've heard my gripe about the current syntax (which Andres appears
to share), but I shan't attempt to prejudice you in favor of my
preferred alternative, because I don't have one yet.

FWIW, I sincerely see very real advantages to what I've proposed here.
To me, the fact that it's convenient to implement is beside the point.

There could be
other ways of avoiding that problem, though. Here's an example:

UPSERT table (keycol1, ..., keycoln) = (keyval1, ..., keyvaln) SET
(nonkeycol1, ..., nonkeycoln) = (nonkeyval1, ..., nonkeyvaln)

That's pretty ugly on multiple levels, and I'm definitely not
proposing that exact thing, but the idea is: look for a record that
matches on the key columns/values; if found, update the non-key
columns with the corresponding values; if not found, construct a new
row with both the key and nonkey column sets and insert it. If no
matching unique index exists we'll have to fail, but we stop short of
having to mention the name of that index.

What if you want to update the key columns - either the potential
conflict-causing one, or another? What about composite unique
constraints? MySQL certainly supports all that, for example.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2013-10-15 10:19:17 -0700, Peter Geoghegan wrote:

On Tue, Oct 15, 2013 at 9:56 AM, Robert Haas <robertmhaas@gmail.com> wrote:

Well, I don't know that any of us can claim to have a lock on what the
syntax should look like.

Sure. But it's not just syntax. We're talking about functional
differences too, since you're talking about mandating an update, which
is a not the same as an "update locked row only conditionally", or a
delete.

I think anything that only works by breaking visibility rules that way
is a nonstarter. Doing that from the C level is one thing, exposing it
this way seems a bad idea.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Oct 15, 2013 at 10:29 AM, Andres Freund <andres@2ndquadrant.com> wrote:

I think anything that only works by breaking visibility rules that way
is a nonstarter. Doing that from the C level is one thing, exposing it
this way seems a bad idea.

What visibility rule is that? Upsert *has* to do effectively the same
thing as what I've proposed - there is no getting away from it. So
maybe the visibility rulebook (which as far as I can tell is "the way
things work today") needs to be updated. If we did, say, INSERT...ON
DUPLICATE KEY UPDATE, we'd have to update a row with potentially no
visible-to-snapshot version *at all*, and make a new version of that
visible. That's just what it takes. What's the difference between that
and just locking? If the only difference is that it isn't necessary to
modify tqual.c because you're passing a tid directly, that isn't a
user-visible difference - the "rule" has been broken just the same.
Arguably, it's even more of a hack, since it's a special, out-of-band
visibility exception. I'm happy to have total scrutiny of changes to
tqual.c, but I'm surprised that the mere fact of it having been
modified is being weighed so heavily.

Another thing that I'm not clear on is how an update can be backed out
of if the row is modified by another xact. As I think I've already
illustrated, the row locking that takes place has to be kind of
opportunistic. I'm sure you could do it, but it would probably be
quite invasive.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 10/15/2013 08:11 AM, Robert Haas wrote:

I'm not saying "go implement MERGE". I'm saying, make the
insert-or-update operation a single statement, using some syntax TBD,
instead of requiring the use of a new insert statement that makes
invisible rows visible as a side effect, so that you can wrap that in
a CTE and feed it to an update statement. That's complex and, AFAICS,
unlike how any other database product handles this.

Hmmm. Is the plan NOT to eventually get to a single-statement upsert?
If not, then I'm not that keen on this feature. I can't say that
anybody I know who's migrating from MySQL would use a 2-statement
version of upsert; if they were prepared for that, then they'd be
prepared to just rewrite their stuff as proper insert/updates anyway.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Oct 15, 2013 at 10:58 AM, Josh Berkus <josh@agliodbs.com> wrote:

Hmmm. Is the plan NOT to eventually get to a single-statement upsert?
If not, then I'm not that keen on this feature.

See the original e-mail in the thread for what I imagine idiomatic
usage will look like.

/messages/by-id/CAM3SWZThwrKtvurf1aWAiH8qThGNMZAfyDcNw8QJu7pqHk5AGQ@mail.gmail.com

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Oct 15, 2013 at 11:05 AM, Peter Geoghegan <pg@heroku.com> wrote:

See the original e-mail in the thread for what I imagine idiomatic
usage will look like.

/messages/by-id/CAM3SWZThwrKtvurf1aWAiH8qThGNMZAfyDcNw8QJu7pqHk5AGQ@mail.gmail.com

Note also that this doesn't preclude a variant with a more direct
update part (not that I think that's all that compelling). Doing
things this way was motivated by:

1) Serving the needs of logical changeset generation plugins, even if
Andres doesn't think that needs to be exposed through SQL. He and I
both want something that does this with low overhead (in particular,
no subtransactions).

2) Getting something effective into the next release. MERGE-like
flexibility seems like a very desirable thing. And the
implementation's infrastructure can be used by an eventual MERGE
implementation.

3) Being simple enough that huge bike shedding over syntax might not
be necessary. Making insert statements grow an update tumor is likely
to get messy fast. I know because I tried it myself.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Peter,

Note also that this doesn't preclude a variant with a more direct
update part (not that I think that's all that compelling). Doing
things this way was motivated by:

I can see the value in the CTE format for this for existing PostgreSQL
users.

(although, AFAICT it doesn't allow for the implementation of one of my
personal desires, which is UPDATE ... ON NOT FOUND INSERT, for cases
where updates are expected to occur 95% of the time, but that's another
topic. Unless "rejects" for an Update could be the leftover rows, but
then we're getting into full MERGE.).

I'm just pointing out that this doesn't do much for the MySQL migration
case; the rewrite is too complex to automate. I'd been assuming that we
had some plans to implement a MySQL-friendly syntax for 9.5, and this
version was a stepping stone to that.

Does this version make a distinction between PRIMARY KEY constraints and
UNIQUE indexes? If not, how does it pick among keys? If so, what about
tables with no PRIMARY KEY for various reasons (like unique GiST indexes?)

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Oct 15, 2013 at 11:23 AM, Josh Berkus <josh@agliodbs.com> wrote:

(although, AFAICT it doesn't allow for the implementation of one of my
personal desires, which is UPDATE ... ON NOT FOUND INSERT, for cases
where updates are expected to occur 95% of the time, but that's another
topic. Unless "rejects" for an Update could be the leftover rows, but
then we're getting into full MERGE.).

This isn't really all that inefficient for that case. Certainly, the
balance in cost between mostly-insert cases and mostly-update cases is
a strength of my basic approach over others.

Does this version make a distinction between PRIMARY KEY constraints and
UNIQUE indexes? If not, how does it pick among keys? If so, what about
tables with no PRIMARY KEY for various reasons (like unique GiST indexes?)

We thought about prioritizing where to look (mostly as a performance
optimization), but right now no. It works with amcanunique methods,
which in practice means btrees. There is no such thing as a GiST
unique index, so I guess you're referring to an exclusion constraint
on an equality operator. That doesn't work with this, but why would
you want it to? As for generalizing this to work with exclusion
constraints, which I guess you might have also meant, that's a much
more difficult and much less compelling proposition, in my opinion.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 10/15/2013 11:38 AM, Peter Geoghegan wrote:

We thought about prioritizing where to look (mostly as a performance
optimization), but right now no. It works with amcanunique methods,
which in practice means btrees. There is no such thing as a GiST
unique index, so I guess you're referring to an exclusion constraint
on an equality operator. That doesn't work with this, but why would
you want it to? As for generalizing this to work with exclusion
constraints, which I guess you might have also meant, that's a much
more difficult and much less compelling proposition, in my opinion.

Yeah, that was one thing I was thinking of.

Also, because you can't INDEX CONCURRENTLY a PK, I've been building a
lot of databases which have no PKs, only UNIQUE indexes. Historically,
this hasn't been an issue because aside from wonky annoyances (like the
CONCURRENTLY case), Postgres doesn't distinguish between UNIQUE indexes
and PRIMARY KEYs -- as, indeed, it shouldn't, since they're both keys,
adn the whole concept of a "primary key" is a legacy of index-organized
databases, which PostgreSQL is not.

However, it does seem like the new syntax could be extended with and
optional "USING unqiue_index_name" in the future (9.5), no?

I'm just checking that we're not painting ourselves into a corner with
this particular implementation. It's OK if it doesn't implement most
things now; it's bad if it is impossible to build on and we have to
support it forever.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Oct 15, 2013 at 11:55 AM, Josh Berkus <josh@agliodbs.com> wrote:

However, it does seem like the new syntax could be extended with and
optional "USING unqiue_index_name" in the future (9.5), no?

There is no reason why we couldn't do that and just consider that one
unique index. Whether we should is another question - I certainly
think that mandating it would be very bad.

I'm just checking that we're not painting ourselves into a corner with
this particular implementation. It's OK if it doesn't implement most
things now; it's bad if it is impossible to build on and we have to
support it forever.

I don't believe it does. In essence this just simply inserts a row,
and rather than throwing a unique constraint violation, locks the row
that prevented insertion from proceeding in respect of any tuple
proposed for insertion where it does not. That's all. You can build
lots of things with it that you can't today. Or you can not use it at
all. So that covers semantics, I'd say.

As for implementation: I believe that the implementation is by far the
most forward thinking (in terms of building infrastructure for a
proper MERGE) of any proposal to date.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 10/15/2013 12:03 PM, Peter Geoghegan wrote:

On Tue, Oct 15, 2013 at 11:55 AM, Josh Berkus <josh@agliodbs.com> wrote:

However, it does seem like the new syntax could be extended with and
optional "USING unqiue_index_name" in the future (9.5), no?

There is no reason why we couldn't do that and just consider that one
unique index. Whether we should is another question -

What's the "shouldn't" argument, if any?

I certainly
think that mandating it would be very bad.

Agreed. If there is a PK, we should allow the user to use it implicitly.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2013-10-15 10:53:35 -0700, Peter Geoghegan wrote:

On Tue, Oct 15, 2013 at 10:29 AM, Andres Freund <andres@2ndquadrant.com> wrote:

I think anything that only works by breaking visibility rules that way
is a nonstarter. Doing that from the C level is one thing, exposing it
this way seems a bad idea.

What visibility rule is that?

The early return you added to HTSMVCC.

At the very least it opens you to lots of halloween problem like
scenarios.

Upsert *has* to do effectively the same thing as what I've proposed -
there is no getting away from it. So maybe the visibility rulebook
(which as far as I can tell is "the way things work today") needs to
be updated. If we did, say, INSERT...ON DUPLICATE KEY UPDATE, we'd
have to update a row with potentially no visible-to-snapshot version
*at all*, and make a new version of that visible. That's just what it
takes. What's the difference between that and just locking? If the
only difference is that it isn't necessary to modify tqual.c because
you're passing a tid directly, that isn't a user-visible difference -
the "rule" has been broken just the same. Arguably, it's even more of
a hack, since it's a special, out-of-band visibility exception.

No, doing it in special case code is fundamentally different since those
locations deal only with one row at a time. There's no scans that can
pass over that row.
That's why I think exposing the "on conflict lock" logic to anything but
C isn't going to fly btw.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2013-10-15 11:23:44 -0700, Josh Berkus wrote:

(although, AFAICT it doesn't allow for the implementation of one of my
personal desires, which is UPDATE ... ON NOT FOUND INSERT, for cases
where updates are expected to occur 95% of the time, but that's another
topic. Unless "rejects" for an Update could be the leftover rows, but
then we're getting into full MERGE.).

FWIW I can't see the above syntax as something working very well - you
fundamentally have to SET every column and it only makes sense in
UPDATEs that provably affect only one row.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers