| 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 | Resend email |
| 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
| 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 |