The visibility map is just 1 bit per page. Vacuum sets these bits to "1" when it sees that all tuples on the page are visible to all transactions. i.e. all tuple xmins are <= the oldest running transaction and none of the tuples have not been marked as deleted by any transaction yet. The visibility map bit will be unset when a new tuple is added to the page or an existing one is "deleted" or more accurately, has the xmax set with the deleting transaction's ID.
The visibility map is stored on-disk as a different fork of the filenode for the table. Two bits are actually stored per page, 1 for visibility and another to mark if the page only contains only frozen tuples. The frozen bit helps reduce the cost of vacuuming the table for transaction wraparound, which is also mentioned in the blog post.
The query planner does not count these bits to determine if it should perform an Index Only Scan vs an Index Scan. An approximate value is stored in pg_class.relallvisible.
The visibility map is stored on-disk as a different fork of the filenode for the table. Two bits are actually stored per page, 1 for visibility and another to mark if the page only contains only frozen tuples. The frozen bit helps reduce the cost of vacuuming the table for transaction wraparound, which is also mentioned in the blog post.
The query planner does not count these bits to determine if it should perform an Index Only Scan vs an Index Scan. An approximate value is stored in pg_class.relallvisible.