Re: testing HS/SR - 1 vs 2 performance

Simon Riggs <simon(at)2ndQuadrant(dot)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.

regards, tom lane