memory layouts for binary search in nbtree

From: Andres Freund <andres(at)anarazel(dot)de>
To: Heikki Linnakangas <hlinnaka(at)iki(dot)fi>, pgsql-hackers(at)postgresql(dot)org
Subject: memory layouts for binary search in nbtree
Date: 2016-05-18 13:25:37
Message-ID: 20160518132537.grcicnutjbl2iwpe@alap3.anarazel.de
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

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.

Andres

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Joshua D. Drake 2016-05-18 13:42:37 Re: Reviewing freeze map code
Previous Message Robert Haas 2016-05-18 12:51:34 Re: Reviewing freeze map code