Re: [HACKERS] memory layouts for binary search in nbtree

2017-06-27 Thread Andres Freund
On 2017-06-27 11:13:38 -0700, Peter Geoghegan wrote: > On Tue, Jun 27, 2017 at 11:04 AM, Andres Freund wrote: > > > > On 2017-06-27 10:57:15 -0700, Peter Geoghegan wrote: > >> I looked at this again recently. I wrote a patch to prove to myself > >> that we can fairly easily

Re: [HACKERS] memory layouts for binary search in nbtree

2017-06-27 Thread Peter Geoghegan
On Tue, Jun 27, 2017 at 11:05 AM, Andres Freund wrote: >> Did you ever try running a pgbench SELECT benchmark, having modified >> things such that all PKs are on columns that are not of type >> int4/int8, but rather are of type numeric? It's an interesting >> experiment, that

Re: [HACKERS] memory layouts for binary search in nbtree

2017-06-27 Thread Peter Geoghegan
On Tue, Jun 27, 2017 at 11:04 AM, Andres Freund wrote: > > On 2017-06-27 10:57:15 -0700, Peter Geoghegan wrote: >> I looked at this again recently. I wrote a patch to prove to myself >> that we can fairly easily reclaim 15 bits from every nbtree internal >> page ItemId, and

Re: [HACKERS] memory layouts for binary search in nbtree

2017-06-27 Thread Andres Freund
On 2016-05-19 19:38:02 -0700, Peter Geoghegan wrote: > On Wed, May 18, 2016 at 6:25 AM, Andres Freund wrote: > > 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

Re: [HACKERS] memory layouts for binary search in nbtree

2017-06-27 Thread Andres Freund
Hi, On 2017-06-27 10:57:15 -0700, Peter Geoghegan wrote: > I looked at this again recently. I wrote a patch to prove to myself > that we can fairly easily reclaim 15 bits from every nbtree internal > page ItemId, and put an abbreviated key there instead. Interesting. Not sure however that really

Re: [HACKERS] memory layouts for binary search in nbtree

2017-06-27 Thread Peter Geoghegan
On Thu, May 19, 2016 at 7:28 PM, Peter Geoghegan wrote: > Abbreviated keys in indexes are supposed to help with this. Basically, > the ItemId array is made to be interlaced with small abbreviated keys > (say one or two bytes), only in the typically less than 1% of pages > that

Re: [HACKERS] memory layouts for binary search in nbtree

2016-05-19 Thread Peter Geoghegan
On Wed, May 18, 2016 at 6:25 AM, Andres Freund wrote: > 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

Re: [HACKERS] memory layouts for binary search in nbtree

2016-05-19 Thread Peter Geoghegan
On Wed, May 18, 2016 at 6:55 AM, Simon Riggs wrote: > I think its a good area of work. I strongly agree. Abbreviated keys in indexes are supposed to help with this. Basically, the ItemId array is made to be interlaced with small abbreviated keys (say one or two bytes),

Re: [HACKERS] memory layouts for binary search in nbtree

2016-05-18 Thread Simon Riggs
On 18 May 2016 at 14:25, Andres Freund 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

[HACKERS] memory layouts for binary search in nbtree

2016-05-18 Thread Andres Freund
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.