VACUUM's "No one parent tuple was found", redux

I've been studying the "No one parent tuple was found" problem some
more, and I've realized there are actually two distinct problems that
manifest at the same place.

Here are test procedures for duplicating the problems on-demand (these
work in either 7.2 or CVS tip):

CASE 1 (transient failure):

1. Start a transaction ("begin;") in one psql window; leave it sitting open.

2. In another psql window, do:

drop table foo;
create table foo (f1 int);

begin;
-- insert at least a few hundred rows of junk data into foo.
-- in the regression database you can do
insert into foo select unique1 from tenk1;
abort;

begin;
insert into foo values(0);
update foo set f1 = f1 + 1;
end;

vacuum full foo;
ERROR: No one parent tuple was found

Repeated vacuum-full attempts will fail as long as the background
transaction remains open; after you close that transaction, it works.

CASE 2 (non-transient failure):

Here, you don't even need a background transaction. Do:

drop table foo;
create table foo (f1 int);

begin;
-- insert at least a few hundred rows of junk data into foo.
-- in the regression database you can do
insert into foo select unique1 from tenk1;
abort;

begin;
insert into foo values(0);
update foo set f1 = f1 + 1;
end;

-- this part is added compared to the transient case:
begin;
update foo set f1 = f1 + 1;
abort;
begin;
select * from foo for update;
insert into foo values(1);
end;

vacuum full foo;
ERROR: No one parent tuple was found

This error is reproducible indefinitely. However, you can clear it by
doing "select * from foo for update" outside any transaction block.
(There are other ways, but that's the easiest non-destructive way.)

The non-transient-failure test procedure is designed to produce a tuple
that has HEAP_XMAX_COMMITTED, HEAP_MARKED_FOR_UPDATE, and t_self
different from t_ctid. This fools the "this tuple is in the chain of
tuples created in updates" test (vacuum.c line 1583 in 7.2 sources).
The second part of the test shouldn't trigger, but does.

The transient-failure test procedure sets up a situation where we have
an updated tuple produced by a transaction younger than the oldest open
transaction (ie, younger than OldestXmin) --- but the immediate parent
tuple of that tuple is dead and gone. I did it by making that
immediate parent be created and deleted in the same transaction. There
may be other ways to get the same effect, but this is certainly one way.

In the given test cases, VACUUM finds *no* tuples that are "recently
dead" per the HeapTupleSatisfiesVacuum test: they're all either
definitely alive or definitely dead and deletable. So no vtlinks
records have been created and you get the "No one parent tuple was
found" error. It's simple to modify the test conditions so that there
are additional tuples that are considered recently dead, and then
you'll get "Parent tuple was not found" instead. (That behavior is
transient, since if there are no other open transactions then no tuples
can be considered recently dead.)

Now, what to do about it? I had previously proposed making sure that
t_ctid is set to t_self whenever we delete or mark4update a tuple.
I still think that's a good idea, but the VACUUM tests (there are two)
should also be changed to ignore tuples that are MARKED_FOR_UPDATE:
instead of

(!(tuple.t_data->t_infomask & HEAP_XMAX_INVALID) &&
!(ItemPointerEquals(&(tuple.t_self),
&(tuple.t_data->t_ctid)))))

the code should be

(!(tuple.t_data->t_infomask & (HEAP_XMAX_INVALID |
HEAP_MARKED_FOR_UPDATE)) &&
!(ItemPointerEquals(&(tuple.t_self),
&(tuple.t_data->t_ctid)))))

A quick look through the sources shows that these two VACUUM tests are
the only places where HEAP_XMAX_INVALID is checked without also checking
for MARKED_FOR_UPDATE. So this bug is a simple oversight that was
created when the mark-for-update feature was added.

It's less clear what to do about the transient error. Clearly, VACUUM
should *not* be assuming that

(tuple.t_data->t_infomask & HEAP_UPDATED &&
!TransactionIdPrecedes(tuple.t_data->t_xmin, OldestXmin))

is sufficient to guarantee that there must be a surviving parent tuple
--- the parent may not have survived scan_heap, if it was created and
deleted in the same transaction.

The conservative approach would be to do what is done now in some other
cases: if we can't find a parent tuple, emit a NOTICE and stop the
repair_frag process, but don't raise a hard error. This would apply
both when vtlinks is null and when we fail to find a match in it.

A more aggressive approach would be to assume that if we didn't find the
parent in vtlinks, it's dead and gone, and we can just bull ahead with
the chain move anyway. While this would be correct and safe in the
test-case scenario, I'm a little nervous about whether any problem could
be created that way.

Comments?

Also, for Mario and Barry: does this test case look anything like what
your real applications do? In particular, do you ever do a SELECT FOR
UPDATE in a transaction that commits some changes, but does not update
or delete the locked-for-update row? If not, it's possible there are
yet more bugs lurking in this area.

regards, tom lane