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.
> 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. But I'd just as soon not use that assumption
here if it's unnecessary. It'd be cheaper anyway to sort and search the
array using plain <, so why are you so eager to use
TransactionIdFollows?
regards, tom lane