Re: WIP patch for latestCompletedXid method of computing snapshot xmax

Tom Lane wrote:
> "Florian G. Pflug" <fgp(at)phlo(dot)org> writes:
>> 2) I don't see how either the childXids array or the XID cache in the proc
>> array could ever not be in ascending xid order. We do guarantee that a
>> child xid is always greater than it's parent.
>
> It's the relationships among siblings that worry me. It's likely that we
> could guarantee this with a bit of care and some Asserts in xact.c's xid-list
> manipulations, but it's not quite obvious that it must be so --- for instance
> using an lcons instead of lappend might break it.

Hm.. AFAICT, a transaction can only ever have currently "live" subtransaction.
In other words, for any node in the transaction tree, all subtrees except for
one are always aborted.

Since we do guarantee that a node has an xid smaller than the of any node below,
it seems the only place we have to be careful at is AtSubCommit_childXids.

>
>> This guarantee enables a few optimizations. First, as you say in the
>> comments, finding the largest xid when committing becomes trivial. But more
>> important, if we can assume that the proc array xid cache is always
>> sorted, we can get ride of the exclusive lock during subxact abort.
>
>> We will *always* remove the last n xids from the cache, so we just need to
>> reset subxids.nxids, and not touch the actual array at all. (We might later
>> set the now-unused entries to InvalidTransactionId, but thats only
>> cosmetic).
>
> I'm not convinced that that works when the subxids cache has overflowed
> earlier in the transaction.

It should. AFAICS, the subxid cache always shows the xids along the "path"
of the transaction tree that leads to the currently active subtransaction.
If it hasn't overflowed, that is. If it has, the list is cut off at some
point. But being cut-off will only make the number of elements we remove
smaller, but not change that we remove some numer of last elements.

> In any case, the bottom line is that it's very unlikely that that code costs
> enough to be worth optimizing. When you think about the total number of
> cycles that have been expended on each subtransaction (especially one that
> has an xid), another comparison or two is lost in the noise. As long as the
> code isn't O(N^2) ... which it isn't AFAICS ... I would rather keep it simple
> and robust.

The real win is that because of the guaranteed order, removing xids from the
cache gets less messy - it reduces to just changing subxids.nxids.Which in turn
allows us to only hold a *shared* proc array lock while doing the removal. To
quote my original mail

"Removing subxids from the proc array cannnot effect xmin
calculations, because the toplevel xid is always small than all it's
children. So we only need to care about snapshots themselves.

But they won't care much if they find an aborted sub xid in the
proc array or now. If not, the xid is neither running nor committed,
so it's assumes to have crashed. If it's in the snapshot, it's
treated as in-progress."

greetings, Florian Pflug