really lazy vacuums?

For historical reasons, what we now think of as VACUUM is referred to
in some portions of the code as "lazy vacuum", to distinguish it from
pre-9.0 VACUUM FULL. As I understand it, VACUUM works like this:

- Scan the relation, accumulating a list of tuples to kill.
- When you get to the end of the relation or when you fill up
maintenance_work_mem, scan each index and kill all index entries
pointing to those tuples.
- Scan the relation a second time and kill the heap tuples.

I'm wondering if there might be some benefit in having an even lazier
type of vacuum that makes only a single scan over the relation and
ignores the indexes. If it hits a tuple that could otherwise be
killed, it marks it LP_DEAD and defragments the page. If it hits a
page with only all-visible tuples, it marks the page PD_ALL_VISIBLE
and sets the visibility map bit. This would be significantly cheaper
than what we normally do right now because it wouldn't touch the
indexes at all, and it would only scan the heap once rather than
twice. The first part is particularly significant for relations where
a high percentage of the visibility map bits area already set, because
we always scan every index in its enitrety even if we only need to
kill a handful of tuples, but we use the visibility map avoid scanning
portions of the heap where no dead tuples can exist. A further
advantage of this approach is that it is very easy to do incrementally
- for example, it'd be perfectly reasonable to scan a 128MB chunk of
the relation and then stop, expecting to do the rest later. That's a
lot less reasonable with our existing approach because you have to
scan all the indexes in their entirety every time. On the downside,
this approach doesn't get rid of any index tuples, nor does it allow
any CTIDs to be reclaimed. But it does reclaim most of the heap
space, and it allows index tuples to be reclaimed opportunistically.
Also, it gets PD_ALL_VISIBLE bits set, which makes scans cheaper and
reduces the cost of later vacuuming.

I'm not quite sure how we'd decide whether to do a "really lazy"
vacuum or the kind we do now. The case where this approach wins big
is when there are few or no dead tuples. In that case, we do a lot of
work looking at the indexes and we don't get much out of it; plus we
scan the heap twice instead of just once. If there are a lot of dead
tuples, then we have to bite the bullet and do the whole thing. It'd
be really nice to find a way to avoid needing to scan the entire index
to reclaim the dead tuples, but unless we're willing to assume that we
can always refind the relevant index tuples based on the heap tuple
(an assumption I believe we have not been willing to make in the
past), it doesn't work - and even if we did make that assumption, it's
not going to be ideal when cleaning out large numbers of index tuples,
because the index I/O will be random rather than sequential as it is
currently.

Thoughts? Does this sound at all feasible/useful? Any ideas on how to tune it?

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company