Postgres Pro
Downloads
Home   >   mailing lists

Re: memory layouts for binary search in nbtree - Mailing list pgsql-hackers

From Simon Riggs
Subject Re: memory layouts for binary search in nbtree
Date
Msg-id CANP8+jLf6ozqc2ie30+--h6oxFUL48jmjQXPS5dpiTFtvtYPYQ@mail.gmail.com
Whole thread Raw
In response to memory layouts for binary search in nbtree  (Andres Freund <andres@anarazel.de>)
Responses Re: memory layouts for binary search in nbtree
List pgsql-hackers
Tree view
On 18 May 2016 at 14:25, Andres Freund <andres@anarazel.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/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

pgsql-hackers by date:

Previous
From: Robert Haas
Date:
Subject: Re: Reviewing freeze map code
Next
From: Victor Yegorov
Date:
Subject: Re: Reviewing freeze map code