Thread: Re: [COMMITTERS] pgsql: Remove O(N^2) performance issue with multiple SAVEPOINTs.
Re: [COMMITTERS] pgsql: Remove O(N^2) performance issue with multiple SAVEPOINTs.
From
Heikki Linnakangas
Date:
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
Re: [COMMITTERS] pgsql: Remove O(N^2) performance issue with multiple SAVEPOINTs.
From
Simon Riggs
Date:
On Tue, Jul 19, 2011 at 8:49 PM, Heikki Linnakangas <heikki.linnakangas@enterprisedb.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
Re: [COMMITTERS] pgsql: Remove O(N^2) performance issue with multiple SAVEPOINTs.
From
Heikki Linnakangas
Date:
On 19.07.2011 23:08, Simon Riggs wrote: > On Tue, Jul 19, 2011 at 8:49 PM, Heikki Linnakangas > <heikki.linnakangas@enterprisedb.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
Re: [COMMITTERS] pgsql: Remove O(N^2) performance issue with multiple SAVEPOINTs.
From
Simon Riggs
Date:
On Tue, Jul 19, 2011 at 9:24 PM, Heikki Linnakangas <heikki.linnakangas@enterprisedb.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
Re: Re: [COMMITTERS] pgsql: Remove O(N^2) performance issue with multiple SAVEPOINTs.
From
Tom Lane
Date:
Heikki Linnakangas <heikki.linnakangas@enterprisedb.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
Re: Re: [COMMITTERS] pgsql: Remove O(N^2) performance issue with multiple SAVEPOINTs.
From
Simon Riggs
Date:
On Thu, Jul 21, 2011 at 5:56 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote: > Heikki Linnakangas <heikki.linnakangas@enterprisedb.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
Re: Re: [COMMITTERS] pgsql: Remove O(N^2) performance issue with multiple SAVEPOINTs.
From
Alvaro Herrera
Date:
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@commandprompt.com> The PostgreSQL Company - Command Prompt, Inc. PostgreSQL Replication, Consulting, Custom Development, 24x7 support
Re: Re: [COMMITTERS] pgsql: Remove O(N^2) performance issue with multiple SAVEPOINTs.
From
Heikki Linnakangas
Date:
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