I am thinking that maintaining fragmented free space within a heap page
might be a good idea. It would help us to reuse the free space ASAP without
waiting for a vacuum run on the page. This in turn will lead to lesser heap
bloats and also increase the probability of placing updated tuple in the
same heap page as the original one.
So during a sequential or index scan, if a tuple is found to be dead, the
corresponding line pointer is marked "unused" and the space is returned to a
free list. This free list is maintained within the page. A linked-list can
be used for this purpose and the special area of the heap-page can be used
to track the fragment list. We can maintain some additional information
about the fragmented space such as, total_free_space, max_fragment_size,
num_of_fragments etc in the special area.
During UPDATEs, if we find that there is no free space in the block, the
fragment list is searched (either first-fit or best-fit), the required space
is consumed and the remaining space is returned to the free list.
We might not be able to reuse the line pointers because indexes may have
references to it. All such line pointers will be freed when the page is
vacuumed during the regular vacuum.