Re: memory layouts for binary search in nbtree

From: Simon Riggs <simon(at)2ndQuadrant(dot)com>
To: Andres Freund <andres(at)anarazel(dot)de>
Cc: Heikki Linnakangas <hlinnaka(at)iki(dot)fi>, PostgreSQL-development <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: memory layouts for binary search in nbtree
Date: 2016-05-18 13:55:36
Views: Raw Message | Whole Thread | Download mbox
Lists: pgsql-hackers

On 18 May 2016 at 14:25, Andres Freund <andres(at)anarazel(dot)de> wrote:

> Hi,
> currently we IIRC use linearly sorted datums for the search in
> individual btree nodes. Not surprisingly that's often one of the
> dominant entries in profiles. We could probably improve upon that by
> using an order more optimized for efficient binary search.
> See e.g. for benchmarks
> showing benefits.

Some stuff from >10 years ago about cache conscious btree layout as well.
That led to adoption of 64kB pages on some benchmarks.

I think its a good area of work.

Simon Riggs
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

In response to


Browse pgsql-hackers by date

  From Date Subject
Next Message Victor Yegorov 2016-05-18 13:55:54 Re: Reviewing freeze map code
Previous Message Robert Haas 2016-05-18 13:45:03 Re: Reviewing freeze map code