Re: Small improvement to compactify_tuples

On Wed, Nov 8, 2017 at 12:59 PM, Andres Freund <andres(at)anarazel(dot)de> wrote:
> I complained about multiple related things, I'm not exactly sure what
> exactly you're referring to here:
> - The fact that HeapTupleHeaderData's are commonly iterated over in
> reverse order is bad for performance. For shared buffers resident
> workloads involving seqscans that yields 15-25% slowdowns for me. It's
> trivial to fix that by just changing iteration order, but that
> obviously changes results. But we could reorder the page during heap
> pruning.

FWIW, the classic page layout (the one that appears in Gray's
Transaction Processing Systems, at any rate) has the ItemId array at
the end of the page and the tuples at the start (immediately after a
generic page header) -- it's the other way around.

I think that that has its pros and cons.

> - The layout of items in index pages is suboptimal. We regularly do
> binary searches over the the linearly ordered items, which is cache
> inefficient. So instead we should sort items as [1/2, 1/4, 3/4, ...]
> elements, which will access items in a close-ish to linear manner.

I still think that we can repurpose each ItemId's lp_len as an
abbreviated key in internal index pages [1], and always get IndexTuple
size through the index tuple header. I actual got as far as writing a
very rough prototype of that. That's obviously a significant project,
but it seems doable.

[1] https://www.postgresql.org/message-id/CAH2-Wz=mV4dmOaPFicRSyNtv2KinxEOtBwUY5R7fXXOC-OearA@mail.gmail.com
--
Peter Geoghegan