pgsql: Remove O(N^2) performance issue with multiple SAVEPOINTs.

Remove O(N^2) performance issue with multiple SAVEPOINTs.
Subtransaction locks now released en masse at main commit, rather than
repeatedly re-scanning for locks as we ascend the nested transaction tree.
Split transaction state TBLOCK_SUBEND into two states, TBLOCK_SUBCOMMIT
and TBLOCK_SUBRELEASE to allow the commit path to be optimised using
the existing code in ResourceOwnerRelease() which appears to have been
intended for this usage, judging from comments therein.

Branch
------
master

Details
-------
http://git.postgresql.org/pg/commitdiff/7cb7122800ec996d4849ce9b4ad3065db19a2aae

Modified Files
--------------
src/backend/access/transam/xact.c | 102 +++++++++++++++++++++++++------------
1 files changed, 70 insertions(+), 32 deletions(-)

On 19.07.2011 19:22, Simon Riggs wrote:
> Remove O(N^2) performance issue with multiple SAVEPOINTs.
> Subtransaction locks now released en masse at main commit, rather than
> repeatedly re-scanning for locks as we ascend the nested transaction tree.
> Split transaction state TBLOCK_SUBEND into two states, TBLOCK_SUBCOMMIT
> and TBLOCK_SUBRELEASE to allow the commit path to be optimised using
> the existing code in ResourceOwnerRelease() which appears to have been
> intended for this usage, judging from comments therein.

CommitSubTransaction(true) does this:

ResourceOwnerRelease(s->curTransactionOwner, RESOURCE_RELEASE_LOCKS,
true, isTopLevel /* == true */);
...
ResourceOwnerDelete(s->curTransactionOwner);

Because isTopLevel is passed as true, ResourceOwnerRelease() doesn't
release or transfer the locks belonging to the resource owner. After the
call, they still point to s->curTransactionOwner. Then, the resource
owner is deleted. After those two calls, the locks still have pointers
to the now-pfree'd ResourceOwner object. Looking at lock.c, we
apparently never dereference LOCALLOCKOWNER.owner field. Nevertheless, a
dangling pointer like that seems like a recipe for trouble. After
releasing all subtransactions, we still fire deferred triggers, for
example, which can do arbitrarily complex things. For example, you might
allocate new resource owners, which if you're really unlucky might get
allocated at the same address as the already-pfree'd resource owner. I'm
not sure what would happen then, but it can't be good.

Instead of leaving the locks dangling to an already-destroyed resource
owner, how about assigning all locks directly to the top-level resource
owner in one sweep? That'd still be much better than the old way of
recursively reassigning them up the subtransaction tree, one level at a
time.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

On Tue, Jul 19, 2011 at 8:49 PM, Heikki Linnakangas
<heikki(dot)linnakangas(at)enterprisedb(dot)com> wrote:
> On 19.07.2011 19:22, Simon Riggs wrote:
>>
>> Remove O(N^2) performance issue with multiple SAVEPOINTs.
>> Subtransaction locks now released en masse at main commit, rather than
>> repeatedly re-scanning for locks as we ascend the nested transaction tree.
>> Split transaction state TBLOCK_SUBEND into two states, TBLOCK_SUBCOMMIT
>> and TBLOCK_SUBRELEASE to allow the commit path to be optimised using
>> the existing code in ResourceOwnerRelease() which appears to have been
>> intended for this usage, judging from comments therein.
>
> CommitSubTransaction(true) does this:
>
> ResourceOwnerRelease(s->curTransactionOwner, RESOURCE_RELEASE_LOCKS, true,
> isTopLevel /* == true */);
> ...
> ResourceOwnerDelete(s->curTransactionOwner);
>
> Because isTopLevel is passed as true, ResourceOwnerRelease() doesn't release
> or transfer the locks belonging to the resource owner. After the call, they
> still point to s->curTransactionOwner. Then, the resource owner is deleted.
> After those two calls, the locks still have pointers to the now-pfree'd
> ResourceOwner object. Looking at lock.c, we apparently never dereference
> LOCALLOCKOWNER.owner field. Nevertheless, a dangling pointer like that seems
> like a recipe for trouble. After releasing all subtransactions, we still
> fire deferred triggers, for example, which can do arbitrarily complex
> things. For example, you might allocate new resource owners, which if you're
> really unlucky might get allocated at the same address as the
> already-pfree'd resource owner. I'm not sure what would happen then, but it
> can't be good.
>
> Instead of leaving the locks dangling to an already-destroyed resource
> owner, how about assigning all locks directly to the top-level resource
> owner in one sweep? That'd still be much better than the old way of
> recursively reassigning them up the subtransaction tree, one level at a
> time.

Yes, I did see what the code was doing.

My feeling was the code was specifically written that way, just never
used. So I wired it up to be used the way intended. Have a look at
ResourceOwnerReleaseInternal()... not code I wrote or touched on this
patch.

You might persuade me to do it another way, but I can't see how to
make that way work. Your case seems a stretch. Not sure why you
mention it now, >7 weeks after review.

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

On 19.07.2011 23:08, Simon Riggs wrote:
> On Tue, Jul 19, 2011 at 8:49 PM, Heikki Linnakangas
> <heikki(dot)linnakangas(at)enterprisedb(dot)com> wrote:
>> On 19.07.2011 19:22, Simon Riggs wrote:
>>>
>>> Remove O(N^2) performance issue with multiple SAVEPOINTs.
>>> Subtransaction locks now released en masse at main commit, rather than
>>> repeatedly re-scanning for locks as we ascend the nested transaction tree.
>>> Split transaction state TBLOCK_SUBEND into two states, TBLOCK_SUBCOMMIT
>>> and TBLOCK_SUBRELEASE to allow the commit path to be optimised using
>>> the existing code in ResourceOwnerRelease() which appears to have been
>>> intended for this usage, judging from comments therein.
>>
>> CommitSubTransaction(true) does this:
>>
>> ResourceOwnerRelease(s->curTransactionOwner, RESOURCE_RELEASE_LOCKS, true,
>> isTopLevel /* == true */);
>> ...
>> ResourceOwnerDelete(s->curTransactionOwner);
>>
>> Because isTopLevel is passed as true, ResourceOwnerRelease() doesn't release
>> or transfer the locks belonging to the resource owner. After the call, they
>> still point to s->curTransactionOwner. Then, the resource owner is deleted.
>> After those two calls, the locks still have pointers to the now-pfree'd
>> ResourceOwner object. Looking at lock.c, we apparently never dereference
>> LOCALLOCKOWNER.owner field. Nevertheless, a dangling pointer like that seems
>> like a recipe for trouble. After releasing all subtransactions, we still
>> fire deferred triggers, for example, which can do arbitrarily complex
>> things. For example, you might allocate new resource owners, which if you're
>> really unlucky might get allocated at the same address as the
>> already-pfree'd resource owner. I'm not sure what would happen then, but it
>> can't be good.
>>
>> Instead of leaving the locks dangling to an already-destroyed resource
>> owner, how about assigning all locks directly to the top-level resource
>> owner in one sweep? That'd still be much better than the old way of
>> recursively reassigning them up the subtransaction tree, one level at a
>> time.
>
> Yes, I did see what the code was doing.
>
> My feeling was the code was specifically written that way, just never
> used. So I wired it up to be used the way intended. Have a look at
> ResourceOwnerReleaseInternal()... not code I wrote or touched on this
> patch.

The way ResourceOwnerReleaseIntenal(isTopLevel==true) works in the case
of a genuine top-level commit doesn't have this problem, because the
sub-resource owners are not deleted until TopTransactionResourceOwner
has been processed, and all the locks released. In fact, before this
patch I think an "Assert(!isTopLevel || owner ==
TopTransactionResourceOwner)" would've be in order in
ResourceOwnerRelease(). Or it could've done "bool isTopLevel = (owner ==
TopTransactionResoureOwner)" in the beginning instead of having
isTopLevel as an argument.

> You might persuade me to do it another way, but I can't see how to
> make that way work. Your case seems a stretch.

You get coincidences with memory allocations surprisingly often, because
things tend to get allocated and free'd in chunks of certain sizes. It's
also pretty fragile in the face of future development. It's not hard to
imagine someone adding code in lock.c to dereference the pointer.

> Not sure why you mention it now,>7 weeks after review.

Because I only just spotted it.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

On Tue, Jul 19, 2011 at 9:24 PM, Heikki Linnakangas
<heikki(dot)linnakangas(at)enterprisedb(dot)com> wrote:

>> You might persuade me to do it another way, but I can't see how to
>> make that way work. Your case seems a stretch.
>
> You get coincidences with memory allocations surprisingly often, because
> things tend to get allocated and free'd in chunks of certain sizes. It's
> also pretty fragile in the face of future development. It's not hard to
> imagine someone adding code in lock.c to dereference the pointer.

Then I think we need a 4th phase (would actually happen first).

I will revoke and rework.

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

Heikki Linnakangas <heikki(dot)linnakangas(at)enterprisedb(dot)com> writes:
> Instead of leaving the locks dangling to an already-destroyed resource
> owner, how about assigning all locks directly to the top-level resource
> owner in one sweep? That'd still be much better than the old way of
> recursively reassigning them up the subtransaction tree, one level at a
> time.

I haven't actually read the patch, but the reason for pushing them up
only one level at a time is that if an intermediate-level subtransaction
aborts, the locks taken by its child subtransactions have to be released
at that time. It sure sounds like this patch broke that.

regards, tom lane

On Thu, Jul 21, 2011 at 5:56 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Heikki Linnakangas <heikki(dot)linnakangas(at)enterprisedb(dot)com> writes:
>> Instead of leaving the locks dangling to an already-destroyed resource
>> owner, how about assigning all locks directly to the top-level resource
>> owner in one sweep? That'd still be much better than the old way of
>> recursively reassigning them up the subtransaction tree, one level at a
>> time.
>
> I haven't actually read the patch, but the reason for pushing them up
> only one level at a time is that if an intermediate-level subtransaction
> aborts, the locks taken by its child subtransactions have to be released
> at that time.  It sure sounds like this patch broke that.

The only path altered by the patch was the
final-commit-while-in-a-subxact, so I don't see a problem in the part
you mention.

At commit all the locks get transferred to the parent, so we scan the
the lock table repeatedly, giving O(N^2).

I think I'll just revert it though. Subtransactions need a lot of
tuning but this isn't high enough up my list to be worth the work.

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

Excerpts from Simon Riggs's message of jue jul 21 13:30:25 -0400 2011:

> I think I'll just revert it though. Subtransactions need a lot of
> tuning but this isn't high enough up my list to be worth the work.

If it works and is sane, why would you revert it?

--
Álvaro Herrera <alvherre(at)commandprompt(dot)com>
The PostgreSQL Company - Command Prompt, Inc.
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

On 21.07.2011 21:05, Alvaro Herrera wrote:
> Excerpts from Simon Riggs's message of jue jul 21 13:30:25 -0400 2011:
>
>> I think I'll just revert it though. Subtransactions need a lot of
>> tuning but this isn't high enough up my list to be worth the work.
>
> If it works and is sane, why would you revert it?

See http://archives.postgresql.org/pgsql-hackers/2011-07/msg01037.php.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com