Re: memory layouts for binary search in nbtree

Hi,

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?

> Can you suggest a workload/hardware to assess the benefits of an
> optimization like this, Andres? Is there a profile available somewhere
> in the archives that shows many cache misses within _bt_binsrch()?

I don't quite remember what triggered my report, but it's quite commonly
visible in any workloads that have btrees above toy sizes, but still
fitting in shared_buffers. Obviously you need somehting where btree
lookups are a significant share of the time, but that's easy enough with
index nested loop joins and such. I do recall seeing it recently-ish in
a number of tpc-h queries.

Greetings,

Andres Freund