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
