Visibility Map Problems

= Introduction =
PostgreSQL tables contain visibility maps (VM), which provide information about which blocks in the table are known to contain only tuples that are visible to all transactions. For such a block, index-only scans need not physically visit the block to confirm that a TID obtained from the index is valid. In PostgreSQL 9.6 and up, the visibility map file also contains data about which blocks are known to contain only frozen tuples.
Corruption of a visibility map can lead to false results from index-only scans, that is returning rows that should not be returned because they have been deleted. In 9.6 and up, corruption can also lead to VACUUM bypassing blocks that need maintenance, which will ultimately result in data corruption. This page discusses ways to detect and fix such problems.
= Known bugs causing VM corruption =
PostgreSQL versions 9.6 (before 9.6.1), 9.5 (before 9.5.5), 9.4 (before 9.4.10), and 9.3 (before 9.3.15) contain a bug that causes failure to make adequate WAL log entries when a VM is truncated as part of truncating its table. A database crash-and-restart shortly after such an event can lead to corrupted VMs. In a replication environment, standby servers will receive incorrect WAL data causing them to create corrupted VMs locally, meaning that standbys are likely to have corrupted data even if the master is valid. However, the effects of this bug are limited to causing incorrect checksums to be generated for VM pages, so that no ill effects will be observed unless the database has checksum generation and checking enabled. If you see checksum complaints about pages in VM files, suspect this bug as the cause.
In PostgreSQL version 9.6 (before 9.6.1), pg_upgrade contains a bug that causes it to generate incorrect VM data if it is running on big-endian hardware. (That excludes Intel-based machines, but many non-Intel architectures such as PPC and Sparc can run big-endian.) If you have used 9.6.0's pg_upgrade on such hardware, you should assume that all VM files in the resulting database are corrupt.
In addition to these known bugs in PostgreSQL itself, operating-system bugs or hardware problems could result in corrupted VM files.
= Detection of broken VM files =
First it is necessary to detect which tables contain corrupt VMs. This analysis method makes use of the extension pg_visibility, so it needs to be enabled first:
CREATE EXTENSION pg_visibility;
Then run the following query, as superuser, to look for corrupted VMs within the current database:
SELECT oid::regclass AS relname
FROM pg_class
WHERE relkind IN ('r', 'm', 't') AND (
 EXISTS (SELECT * FROM pg_check_visible(oid))
 OR EXISTS (SELECT * FROM pg_check_frozen(oid)));
If this returns an empty list, the current database contains no problems. If not, the listed tables contain corrupt VM data that needs to be repaired. See below for more details. 
Be sure to repeat this test in each database of the cluster. In a replicated configuration, you'll need to check each standby individually, along with the master.
In PostgreSQL releases before 9.6, the pg_visibility extension does not exist, so this direct test for bad data is not possible. Suspect VM corruption if a query that uses an index-only scan (as shown by EXPLAIN) gives wrong results, but turning off enable_indexonlyscan causes it to give correct results. Also, a checksum complaint about a block in a VM file is of course evidence of corruption.
= Cleanup of broken VM files =
When using the pg_visibility extension, it's sufficient to apply the pg_truncate_visibility_map() function to each table that is identified as having a problem. You can automate that by just calling it as part of the query given above:
SELECT oid::regclass AS relname, pg_truncate_visibility_map(oid)
FROM pg_class
WHERE relkind IN ('r', 'm', 't') AND (
 EXISTS (SELECT * FROM pg_check_visible(oid))
 OR EXISTS (SELECT * FROM pg_check_frozen(oid)));
Remember to do this in each database. Afterwards, you may wish to VACUUM each repaired table to rebuild up-to-date VM data. However, that is not urgent unless you are very reliant on high performance of index-only scans. Autovacuum can be expected to rebuild the VMs eventually, except perhaps those for nearly-read-only tables.
In a replicated configuration, if you have found that any standby servers have corrupted VM files that are not also corrupt on the master, you will need to do pg_truncate_visibility_map() on those tables on the master, so that the truncation and subsequent rebuild propagate to the standby.
If you are not using the pg_visibility extension, perhaps because you are on a pre-9.6 release, you can fix broken VM files simply by deleting them by hand while the server is stopped. The file name to delete can be determined by 
SELECT pg_relation_filepath('name of damaged table') || '_vm'
See Free Space Map Problems for additional discussion --- this is much like cleanup of a broken FSM, except that the name of the file to delete ends in "vm" not "fsm".