Re: advance local xmin more aggressively
advance local xmin more aggressively
От:
Jeff Davis <pgsql@j-davis.com>
Дата:
With the new snapshot maintenance code, it looks like we can advance the xmin more aggressively. For instance: S1: INSERT INTO foo VALUES(1); S2: BEGIN; DECLARE c1 CURSOR FOR SELECT i FROM foo; S1: DELETE FROM foo; S2: DECLARE c2 CURSOR FOR SELECT i FROM foo; CLOSE c1; S1: VACUUM VERBOSE foo; The VACUUM should be able to clean up the deleted tuple, because it's no longer visible to anyone. Attached a small patch to accomplish this. I don't expect it to be put in 8.4, but it's small enough that I thought I should at least send it in just in case. Regards, Jeff Davis
Re: advance local xmin more aggressively
От:
Heikki Linnakangas <hlinnakangas@vmware.com>
Дата:
On 12/09/2014 10:35 PM, Robert Haas wrote: > On Mon, Dec 8, 2014 at 9:31 AM, Robert Haas wrote: >> On Mon, Dec 8, 2014 at 4:56 AM, Heikki Linnakangas >> wrote: >>> I don't immediately see the problem either, but I have to say that >>> grovelling through all the resource owners seems ugly anyway. Resource >>> owners are not meant to be traversed like that. And there could be a lot of >>> them, and you have to visit every one of them. That could get expensive if >>> there are a lot of resource owners. >> >> 1. I don't really see why resource owners shouldn't be traversed like >> that. They are clearly intended to form a hierarchy, and there's >> existing code that recurses through the hierarchy from a given level >> downward. What's ugly about that? I can't exactly point my finger on it, but it just feels wrong from a modularity point of view. Their purpose is to make sure that we don't leak resources on abort, by allowing easy an "release everything" operation. It's not designed for finding objects based on some other criteria. There is similar double bookkeeping of many other things that are tracked by resource owners. Heavy-weight locks are tracked by LOCALLOCK structs, buffer pins in PrivateRefCount array etc. Those things existed before resource owners were invented, but if we were starting from scratch, that design would still make sense, as different objects have different access criteria. fd.c needs to be able to find the least-recently-used open file, for example, and you need to find the snapshot with the lowest xmin. > Upthread, I suggested keeping a tally of the number of snapshots with > the advertised xmin and recomputing the xmin to advertise only when it > reaches 0. This patch doesn't implementation that optimization, but > it does have code that aborts the traversal of the resource owner > hierarchy as soon as we see an xmin that will preclude advancing our > advertised xmin. Releasing N resource owners could therefore cost > O(N^2) in the worst case, but note that releasing N resource owners is > *already* an O(N^2) operation in the worst case, because the list of > children of a particular parent resource owner is singly linked, and > thus deleting a resource owner is O(N). It's been that way for an > awfully long time without anyone complaining, probably because (a) > it's not particularly common to have large numbers of cursors open > simultaneously and (b) even if you do have that, the constant factor > is pretty low. I think you're confusing the N and the N above. It's true that deleting a resource owner is O(M), where the M is the number of children of that resource owner. It does not follow that releasing N resource owners is O(N^2), where N is the number of resource owners released. Calling ResourceOwnerDelete(x) will only visit each resource owner in that tree once, so it's O(N), where N is the total number of resource owners in the tree. I did some testing of the worst case scenario. The attached script first creates a lot of cursors, then a lot of savepoints, and finally closes the cursors in FIFO order. When the number of savepoints is high enough, this actually segfaults with your patch, because you run out of stack space when recursing the subxact resource owners. That's hardly this patch's fault, I'm actually surprised it doesn't crash without it, because we recurse into all resource owners in ResourceOwnerRelease too. Apparently the subxacts are closed in LIFO order at commit, but there might be are other cases where you could trigger that. In any case, a stack-depth check would be nice. - Heikki
Re: advance local xmin more aggressively
От:
Heikki Linnakangas <hlinnakangas@vmware.com>
Дата:
On 12/10/2014 08:35 PM, Robert Haas wrote: > On Wed, Dec 10, 2014 at 12:57 PM, Heikki Linnakangas > wrote: >> Clever. Could we use that method in ResourceOwnerReleaseInternal and >> ResourceOwnerDelete, too? Might be best to have a >> ResourceOwnerWalk(resowner, callback) function for walking all resource >> owners in a tree, instead of one for walking the snapshots in them. > > Sure. It would be a little more complicated there since you want to > stop when you get back to the starting point, but not too bad. But is > that solving any actual problem? I thought that a transaction commit or abort in some special circumstances might call ResourceOwnerReleaseInternal on the top level, but I can't make it happen. The machinery in xact.c is too clever, and always releases the resource owners from the bottom up. And I can't find a way to create a deep resource owner tree in any other way. So I guess it's fine as it is. MemoryContextCheck and MemoryContextPrint also recurse, however. MemoryContextCheck is only enabled with --enable-cassert, but MemoryContextPrint is called when you run out of memory. That could turn a plain "out of memory" error into a stack overrun, triggering a server crash and restart. >> It occurs to me that the pairing heap I just posted in another thread >> (http://www.postgresql.org/message-id/54886BB8.9040000@vmware.com) would be >> a good fit for this. It's extremely cheap to insert to and to find the >> minimum item (O(1)), and the delete operation is O(log N), amortized. I >> didn't implement a delete operation, for removing a particular node, I only >> did delete-min, but it's basically the same code. Using a pairing heap for >> this might be overkill, but if we have that implementation anyway, the code >> in snapmgr.c to use it would be very simple, so I see little reason not to. >> It might even be simpler than your patch, because you wouldn't need to have >> the heuristics on whether to attempt updating the xmin; it would be cheap >> enough to always try it. > > Care to code it up? Here you are. - Heikki
Re: advance local xmin more aggressively
От:
Heikki Linnakangas <hlinnakangas@vmware.com>
Дата:
On 12/16/2014 10:41 PM, Jeff Janes wrote: > On Wed, Dec 10, 2014 at 3:46 PM, Robert Haas wrote: >> >> On Wed, Dec 10, 2014 at 3:28 PM, Heikki Linnakangas >> wrote: >>>> Care to code it up? >>> >>> Here you are. >> >> That was quick. >> >> You need to add a semicolon to the end of line 20 in pairingheap.c. > > In addition to the semicolon, it doesn't build under cassert. There are > some pairingheap_empty that need to be pairingheap_is_empty, and snapmgr.c > needs an address of operator near line 355 and something is wrong > in snapmgr.c near line 811. Here's an updated version, rebased over the pairing heap code that I just committed, and fixing those bugs. - Heikki
Re: advance local xmin more aggressively
От:
Robert Haas <robertmhaas@gmail.com>
Дата:
On Wed, Dec 10, 2014 at 9:49 AM, Robert Haas wrote: > I guess this bears some further thought. I certainly don't like the > fact that this makes the whole system crap out at a lower number of > subtransactions than presently. The actual performance numbers don't > bother me very much; I'm comfortable with the possibility that closing > a cursor will be some modest percentage slower if you've got thousands > of active savepoints. Here's a new version with two changes: 1. I changed the traversal of the resource owner tree to iterate instead of recurse. It now does a depth-first, pre-order traversal of the tree; when we reach the last child of a node, we follow its parent pointer to get back to where we were. That way, we don't need to keep anything on the stack. That fixed the crash at 100k cursors, but it was still 4x slower. 2. Instead of traversing the tree until we find an xmin equal to the one we're currently advertising, the code now traverses the entire tree each time it runs. However, it also keeps a record of how many times the oldest xmin occurred in the tree, which is decremented each time we unregister a snapshot with that xmin; the traversal doesn't run again until that count reaches 0. That fixed the performance regression on your test case. With a million subtransactions: master 34.464s 33.742s 34.317s advance-xmin 34.516s 34.069s 34.196s -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
Re: advance local xmin more aggressively
От:
Robert Haas <robertmhaas@gmail.com>
Дата:
On Mon, Dec 8, 2014 at 9:31 AM, Robert Haas wrote: > On Mon, Dec 8, 2014 at 4:56 AM, Heikki Linnakangas > wrote: >> I don't immediately see the problem either, but I have to say that >> grovelling through all the resource owners seems ugly anyway. Resource >> owners are not meant to be traversed like that. And there could be a lot of >> them, and you have to visit every one of them. That could get expensive if >> there are a lot of resource owners. > > 1. I don't really see why resource owners shouldn't be traversed like > that. They are clearly intended to form a hierarchy, and there's > existing code that recurses through the hierarchy from a given level > downward. What's ugly about that? Here's a patch. I looked at the issue of tracking parent-less resource owners a bit more closely. It turns out that resource owners are always created in TopMemoryContext "since they should only be freed explicitly" (cf. resowner.c). I was a bit worried about that, because it would be bad to keep a list of all parent-less resource owners if list elements could vanish in a context reset. But that doesn't seem to be a concern. So I stole the nextchild links of parent-less resource owners, which are not used for anything currently, to keep a list of such resource owners. It occurred to me that there's probably not much value in recomputing xmin when the active snapshot stack is non-empty. It's not impossible that a PL/pgsql function could close a cursor with an old xmin and then do lots of other work (or just sleep for a long time) before returning to the top-level, but it is pretty unlikely. So the attached patch only considers recomputing the advertised xmin when the active snapshot stack is empty. That'll happen at the end of each statement, which seems soon enough. Upthread, I suggested keeping a tally of the number of snapshots with the advertised xmin and recomputing the xmin to advertise only when it reaches 0. This patch doesn't implementation that optimization, but it does have code that aborts the traversal of the resource owner hierarchy as soon as we see an xmin that will preclude advancing our advertised xmin. Releasing N resource owners could therefore cost O(N^2) in the worst case, but note that releasing N resource owners is *already* an O(N^2) operation in the worst case, because the list of children of a particular parent resource owner is singly linked, and thus deleting a resource owner is O(N). It's been that way for an awfully long time without anyone complaining, probably because (a) it's not particularly common to have large numbers of cursors open simultaneously and (b) even if you do have that, the constant factor is pretty low. Following Heikki's previous suggestion, the patch contains checks to make sure that we find exactly the number of registered snapshots that we expect to find. We could consider demoting these to asserts or something, but this is more likely to catch bugs if there are any. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
Re: advance local xmin more aggressively
От:
Jeff Janes <jeff.janes@gmail.com>
Дата:
On Wed, Dec 10, 2014 at 3:46 PM, Robert Haas <robertmhaas@gmail.com> wrote:
Cheers,
Jeff
On Wed, Dec 10, 2014 at 3:28 PM, Heikki Linnakangas
<hlinnakangas@vmware.com> wrote:
>> Care to code it up?
>
> Here you are.
That was quick.
You need to add a semicolon to the end of line 20 in pairingheap.c.
In addition to the semicolon, it doesn't build under cassert. There are some pairingheap_empty that need to be pairingheap_is_empty, and snapmgr.c needs an address of operator near line 355 and something is wrong in snapmgr.c near line 811.
Cheers,
Jeff
