Yeah, you're right, I believe that every code path in VACUUM that
leads to the visibility map bit being set also leads to all remaining
tuples on the page being frozen. So in a world without heap pruning,
frozen should be a reliable proxy for "value of the tuple the last
time it was added to the counter". If you count -1 for a frozen
tuple, and 1 for a visible tuple, you should end up at precisely the
delta from the last time the page was turned visible.
It seems to me that with this definition of delta, the concurrent
COUNT(*) case is fine. The counter isn't affected by the dirtying of
the page, nor is the delta for the page. The result will be
completely consistent with what it would have been had the page dirty
never happened. But concurrent VACUUM under this definition fails. So
yeah, I'll drop this until I have a concrete idea of how (or if) to
proceed. Thanks for the feedback.