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. Thanks, Pavan EnterpriseDB http://www.enterprisedb.com