Re: [HACKERS] memory layouts for binary search in nbtree - Mailing list pgsql-hackers

From Andres Freund
Subject Re: [HACKERS] memory layouts for binary search in nbtree
Date
Msg-id 20170627185405.bcbsxthjv5j5btvl@alap3.anarazel.de
Whole thread Raw
In response to Re: [HACKERS] memory layouts for binary search in nbtree  (Peter Geoghegan <pg@bowt.ie>)
List pgsql-hackers
On 2017-06-27 11:13:38 -0700, Peter Geoghegan wrote:
> On Tue, Jun 27, 2017 at 11:04 AM, Andres Freund <andres@anarazel.de> wrote:
> >
> > On 2017-06-27 10:57:15 -0700, Peter Geoghegan wrote:
> >> I looked at this again recently. I wrote a patch to prove to myself
> >> that we can fairly easily reclaim 15 bits from every nbtree internal
> >> page ItemId, and put an abbreviated key there instead.
> >
> > Interesting. Not sure however that really addresses my layout / cache
> > efficiency concern? Or is that just a largely independent optimization,
> > except it's affecting the same area of code?
> 
> Well, you'd only do this on internal pages, which are a tiny minority
> of the total, and yet are where the majority of binary searches for an
> index scan occur in practice. The optimization has the effect of
> making the binary search only need to access the much smaller ItemId
> array in that best case. In the best case, where you resolve all
> comparisons on internal pages, you still have to get the index tuple
> that you need to follow the TID of to go to a page on the next level
> down, once the binary search for an internal page actually finds it.
> But that's all.
> 
> In the best case, and maybe the average case, this could be highly
> effective, I think. There would definitely be cases where the
> optimization wouldn't help at all, but hopefully it would also not
> hurt.

In other words, it's an independent optimization.  That's cool, but I'd
rather talk about it in an independent thread, to avoid conflating the
issues.



pgsql-hackers by date:

Previous
From: Andres Freund
Date:
Subject: Re: [HACKERS] Fast promotion not used when doing a recovery_targetPITR restore?
Next
From: Tom Lane
Date:
Subject: Re: [HACKERS] Reducing pg_ctl's reaction time