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
Message-ID: CANP8+jLf6ozqc2ie30+--h6oxFUL48jmjQXPS5dpiTFtvtYPYQ@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox
Thread:
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. http://cglab.ca/~morin/misc/arraylayout/ 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 http://www.2ndQuadrant.com/
<http://www.2ndquadrant.com/>
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

In response to

Responses

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