Skip site navigation (1) Skip section navigation (2)

Re: testing HS/SR - 1 vs 2 performance

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: Simon Riggs <simon(at)2ndQuadrant(dot)com>
Cc: Heikki Linnakangas <heikki(dot)linnakangas(at)enterprisedb(dot)com>, Erik Rijkers <er(at)xs4all(dot)nl>, pgsql-hackers(at)postgresql(dot)org
Subject: Re: testing HS/SR - 1 vs 2 performance
Date: 2010-04-16 15:10:45
Message-ID: 9479.1271430645@sss.pgh.pa.us (view raw or flat)
Thread:
Lists: pgsql-hackers
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

In response to

Responses

pgsql-hackers by date

Next:From: Simon RiggsDate: 2010-04-16 21:00:09
Subject: Re: testing HS/SR - 1 vs 2 performance
Previous:From: Simon RiggsDate: 2010-04-16 14:52:49
Subject: Re: testing HS/SR - 1 vs 2 performance

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group