On Fri, Dec 28, 2018 at 3:20 PM Heikki Linnakangas <hlinnaka@iki.fi> wrote:
> 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.
Ah, right. I think I see what you mean now.
I like that this datastructure explicitly has a place for the new
item, so you really do "pretend it's already on the page". Maybe
that's what you liked about it as well.
I'm a little concerned about the cost of maintaining the data
structure. This sounds workable, but we probably don't want to
allocate a buffer most of the time, or even hold on to the information
most of the time. The current design throws away potentially useful
information that it may later have to recreate, but even that has the
benefit of having little storage overhead in the common case.
Leave it with me. I'll need to think about this some more.
--
Peter Geoghegan