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-17 15:13:46
Message-ID: (view raw, whole thread or download thread mbox)
Lists: pgsql-hackers
Simon Riggs <simon(at)2ndQuadrant(dot)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

			regards, tom lane

In response to


pgsql-hackers by date

Next:From: Robert HaasDate: 2010-04-17 15:25:46
Subject: Re: testing HS/SR - 1 vs 2 performance
Previous:From: Robert HaasDate: 2010-04-17 15:11:29
Subject: Re: Invitation to connect on LinkedIn

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