On Fri, 2010-04-16 at 11:10 -0400, Tom Lane wrote:
> Simon Riggs <simon@2ndQuadrant.com> writes:
> > On Fri, 2010-04-16 at 10:39 -0400, Tom Lane wrote:
> >> I think you're outsmarting yourself there. A binary search will in fact
> >> *not work* with circular xid comparison (this is exactly why there's no
> >> btree opclass for XID).
>
> > I don't understand the exact, please explain more.
> > I'm not using bsearch() just a quick chop based upon xid comparison,
> > which looks to me like it will work.
>
> Implementing it yourself doesn't get you out of the fact that it won't
> work. Consider
>
> 1 2 3 ... 3000000000 ... 3999999999
>
> and suppose that 3000000000 is the array's middle element. If you
> search for 100, your first probe will conclude that it is to the right
> of 3000000000, which is the wrong direction. Binary search, or indeed
> the entire concept that the array is "sorted" in the first place,
> depends on a transitive comparison operator. TransactionIdFollows does
> not satisfy the transitive law.
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 and in this example we have 7 values in the
current array, with tail at W-3 and head at 5. Note the gap between W
and 3 where we would skip the values 1 and 2 because they are special.
Each element's xid is TransactionIdAdvanced(previous element).
So when we search for value 3 we would start from W, then decide it is
to the right, which is correct and continue from there.
The values are laid out in TransactionIdFollows order, not in numeric
order, hence we need to use TransactionIdFollows to decide which way to
branch.
As long as it works I'm not worried if the array is not technically
"sorted".
-- Simon Riggs www.2ndQuadrant.com