Re: Making all nbtree entries unique by having heap TIDs participate in comparisons

On 29/12/2018 01:04, Peter Geoghegan wrote:
>> However, naively computing the penalty upfront for every offset would be
>> a bit wasteful. Instead, start from the middle of the page, and walk
>> "outwards" towards both ends, until you find a "good enough" penalty.
>
> You can't start at the middle of the page, though.
>
> You have to start at the left (though you could probably start at the
> right instead). This is because of page fragmentation -- it's not
> correct to assume that the line pointer offset into tuple space on the
> page (firstright linw pointer lp_off for candidate split point) tells
> you anything about what the space delta will be after the split. You
> have to exhaustively add up the free space before the line pointer
> (the free space for all earlier line pointers) before seeing if the
> line pointer works as a split point, since each previous line
> pointer's tuple could be located anywhere in the original page's tuple
> space (anywhere to the left or to the right of where it would be in
> the simple/unfragmented case).

Right. You'll need to do the free space computations from left to right,
but once you have done that, you can compute the penalties in any order.

I'm envisioning that you have an array, with one element for each item
on the page (including the tuple we're inserting, which isn't really on
the page yet). In the first pass, you count up from left to right,
filling the array. Next, you compute the complete penalties, starting
from the middle, walking outwards.

That's not so different from what you're doing now, but I find it more
natural to explain the algorithm that way.

- Heikki