TODO item: Allow data to be pulled directly from indexes

Sometime last year, a discussion started about including visibility
metadata to avoid heap fetches during an index scan:

http://archives.postgresql.org/pgsql-patches/2007-10/msg00166.php
http://archives.postgresql.org/pgsql-patches/2008-01/msg00049.php

I think the last discussion on this was in April:

http://archives.postgresql.org/pgsql-hackers/2008-04/msg00618.php (last
item)

I have worked with the current patch, and I have some thoughts about
that approach and the approaches listed in the TODO item. The TODO lists
three approaches, in short

(1) Add a bit for an index tuple that indicates "visible" or "maybe
visible."
(2) Use a per-table bitmap that indicates which pages have at least one
tuple that is not visible to all transactions.
(3) Same as (2) but at the granularity of one bit per table.

The approach in the patch is different:

(4) Add transaction ids, etc to the index tuple (totaling 16 bytes)

I would group (1) & (4) together and (2) & (3) together. I think the
time and space trade-offs are pretty obvious, so I won't waste time on
those.

(1) & (4) require an UPDATE or DELETE to twiddle the old index tuple.
Tom has noted (in the linked message) that this is not reliable if the
index has any expression-valued columns, because it is not always
possible to find the old index entry. For this reason, the proposed
patch does not keep visibility metadata for indexes on expressions. This
seems like a reasonable limitation --- indexed expressions are just less
efficient.

The main difference between (1) & (4) is that (1) will sometimes require
heap lookups and (4) never will. Moreover, the heap lookups in (1) will
be difficult for the optimizer to estimate, unless some special
statistics can be maintained for this purpose.

I should mention there is a major flaw in the patch, because it puts
pointers to HOT tuples in the index, in order to capture the different
transaction ids in the chain. I think this can be fixed by only pointing
to the root of the HOT chain, and setting xmin/xmax to the entire range
of transaction ids spanned by the chain. I'm not sure about all the
details (the ctid and some other bits also need to be set).

(2) & (3) can work for any index, and they are quite elegant in the way
that the overhead does not change with the number of indexes. The TODO
also notes the benefit of (2) for efficient vacuuming. Thus, I think
that (2) is a great idea in general, but it does not serve the intended
purpose of this TODO item. Once a page gets marked as requiring
visibility checks, it cannot be unmarked until the next VACUUM. The
whole point of this feature is that we are willing to be more proactive
during updates in order to make index access more efficient.

So in summary, I think that (2) would be nice as a separate feature,
with (1) and (4) being more favorable for index-only scans. The obvious
trouble with (4) is the extra space overhead. There are also issues with
correctness that I mentioned (any thoughts here would be appreciated).
Other than that, I would favor (4) because it offers the most stable
performance.

Please let me know if you agree/disagree with anything here. I need to
get this feature implemented for my research, but I would also love to
contribute it to the community so your opinions matter a lot.