Re: memory layouts for binary search in nbtree

On Tue, Jun 27, 2017 at 11:04 AM, Andres Freund <andres(at)anarazel(dot)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.

--
Peter Geoghegan