Re: testing HS/SR - 1 vs 2 performance - Mailing list pgsql-hackers

On Sat, 2010-04-17 at 11:13 -0400, Tom Lane wrote:
> Simon Riggs <simon@2ndQuadrant.com> writes:
> > AFAICS the example you give isn't correct.
> 
> > We would lay out the values like this
> 
> > W-3 W-2 W-1 W 3 4 5
> 
> > where W is the wrap value
> 
> Stop right there, you're already failing to think clearly.  There is no
> unique "wrap value", all values act the same in circular XID space.
> 
> The fundamental problem here is that if the set of XIDs involved spans a
> sufficiently long range, your array will have a[0] < a[1] < ... < a[n]
> but it will fail to be true that a[0] < a[n].  If that's also true for,
> say, a[0] vs the midpoint element, then a binary search for a[0] will
> fail because it will make the wrong decision while probing the midpoint.

I understand that the xids are circular, but there is only one point
where the next xid has a lower integer value but is still "later" from
the perspective of TransactionIdFollows. Apart from that single
discontinuity all other values are monotonic. From your insistence I
presume I must be missing something, but I just don't see it. Perhaps we
are just misunderstanding each other about the "sufficiently long
range".

> > The values are laid out in TransactionIdFollows order,
> 
> They *cannot* be "laid out in TransactionIdFollows order".  It's not
> possible, because that relationship isn't a total ordering.
> 
> Now it might be the case that this is OK for HS purposes because the set
> of XIDs that are relevant at any one instant should never span more than
> half of the XID space.

Agree that is true.

>  But I'd just as soon not use that assumption
> here if it's unnecessary. 

I understand what your saying. I think it is necessary here.

>  It'd be cheaper anyway to sort and search the
> array using plain <, so why are you so eager to use
> TransactionIdFollows?

The array grows to the right and is laid out one xid per element,
resulting in a sequence of values that are transactionid-monotonic. As
the values increase there will eventually reach the discontinuity where
they cease being normally monotonic. Doing it this way means that we can
add rows past the head of the array and then move the head atomically,
so that we can make adding xids lock-free.

If we try to actually sort the values then the algorithm is both more
complex and requires locking. It would be easier to just remember where
the discontinuity is and act accordingly.

So I'm not eager to use either way, but I only currently see one way
that would work.

If there's a different way, that gives the same or better algorithmic
characteristics, I will be happy to code it.

-- Simon Riggs           www.2ndQuadrant.com