Heap truncation without AccessExclusiveLock (9.4)

Truncating a heap at the end of vacuum, to release unused space back to
the OS, currently requires taking an AccessExclusiveLock. Although it's
only held for a short duration, it can be enough to cause a hiccup in
query processing while it's held. Also, if there is a continuous stream
of queries on the table, autovacuum never succeeds in acquiring the
lock, and thus the table never gets truncated.

I'd like to eliminate the need for AccessExclusiveLock while truncating.

Design
------

In shared memory, keep two watermarks: a "soft" truncation watermark,
and a "hard" truncation watermark. If there is no truncation in
progress, the values are not set and everything works like today.

The soft watermark is the relation size (ie. number of pages) that
vacuum wants to truncate the relation to. Backends can read pages above
the soft watermark normally, but should refrain from inserting new
tuples there. However, it's OK to update a page above the soft
watermark, including adding new tuples, if the page is not completely
empty (vacuum will check and not truncate away non-empty pages). If a
backend nevertheless has to insert a new tuple to an empty page above
the soft watermark, for example if there is no more free space in any
lower-numbered pages, it must grab the extension lock, and update the
soft watermark while holding it.

The hard watermark is the point above which there is guaranteed to be no
tuples. A backend must not try to read or write any pages above the hard
watermark - it should be thought of as the end of file for all practical
purposes. If a backend needs to write above the hard watermark, ie. to
extend the relation, it must first grab the extension lock, and raise
the hard watermark.

The hard watermark is always >= the soft watermark.

Shared memory space is limited, but we only need the watermarks for any
in-progress truncations. Let's keep them in shared memory, in a small
fixed-size array. That limits the number of concurrent truncations that
can be in-progress, but that should be ok. To not slow down common
backend operations, the values (or lack thereof) are cached in relcache.
To sync the relcache when the values change, there will be a new shared
cache invalidation event to force backends to refresh the cached
watermark values. A backend (vacuum) can ensure that all backends see
the new value by first updating the value in shared memory, sending the
sinval message, and waiting until everyone has received it.

With the watermarks, truncation works like this:

1. Set soft watermark to the point where we think we can truncate the
relation. Wait until everyone sees it (send sinval message, wait).

2. Scan the pages to verify they are still empty.

3. Grab extension lock. Set hard watermark to current soft watermark (a
backend might have inserted a tuple and raised the soft watermark while
we were scanning). Release lock.

4. Wait until everyone sees the new hard watermark.

5. Grab extension lock.

6. Check (or wait) that there are no pinned buffers above the current
hard watermark. (a backend might have a scan in progress that started
before any of this, still holding a buffer pinned, even though it's empty.)

7. Truncate relation to the current hard watermark.

8. Release extension lock.

If a backend inserts a new tuple before step 2, the vacuum scan will see
it. If it's inserted after step 2, the backend's cached soft watermark
is already up-to-date, and thus the backend will update the soft
watermark before the insert. Thus after the vacuum scan has finished the
scan at step 2, all pages above the current soft watermark must still be
empty.

Implementation details
----------------------

There are three kinds of access to a heap page:

A) As a target for new tuple.
B) Following an index pointer, ctid or similar.
C) A sequential scan (and bitmap heap scan?)

To refrain from inserting new tuples to non-empty pages above the soft
watermark (A), RelationGetBufferForTuple() is modified to check the soft
watermark (and raise it if necessary).

An index scan (B) should never try to read beyond the high watermark,
because there are no tuples above it, and thus there should be no
pointers to pages above it either.

A sequential scan (C) must refrain from reading beyond the hard
watermark. This can be implemented by always checking the (cached) high
watermark value before stepping to next page.

Truncation during hot standby is a lot simpler: set soft and hard
watermarks to the truncation point, wait until everyone sees the new
values, and truncate the relation.

Does anyone see a flaw in this?

- Heikki