Re: memory layouts for binary search in nbtree

On Wed, May 18, 2016 at 6:55 AM, Simon Riggs <simon@2ndquadrant.com> wrote:
> I think its a good area of work.

I strongly agree.

Abbreviated keys in indexes are supposed to help with this. Basically,
the ItemId array is made to be interlaced with small abbreviated keys
(say one or two bytes), only in the typically less than 1% of pages
that are internal (leaf page binary searches don't change). Those
internal pages naturally have a wide range of values represented, so 1
byte turns out to be a lot more than you'd think. And, you only have
to generate a new one when there is a pagesplit, which is relatively
infrequent. You could squeeze out the lp_len bits to fit the
abbreviated keys, and store that in the IndexTuple proper. I've
discussed this idea with Mashahiko extensively in private. I have lots
of related ideas, and think it's a very promising area.

I think that this project will be very difficult without better testing.

This idea also enables complementary techniques, like interpolation
search that can degrade to binary search.

-- 
Peter Geoghegan