> 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.
Maintaining a list like that seems like a lot of hassle to me. Instead, you could just scan the line pointers looking for a dead tuple of the right size. We already have to scan the line pointers when inserting to find a free line pointer.
That's a good suggestion. Just to avoid useless scans when there is no fragment which can accommodate the new tuple, we may have some book keeping information in the special area though.