News for hackers. Stuff that matters.
Re:The State of Vacuum in Postgres by devit on Friday January 05, 2018 @05:40PM (#16082399)
Sure, but the DB knows what transactions are active.

Assuming active transactions {T}_i ordered by id, then if you are committing T_i, any row whose [Tmin, Tmax] visibility interval is fully contained in (T_(i-1), T_(i+1)) (i.e. for which Tmin > T_(i-1) && T_(i+1) < Tmax) is now dead (taking -inf and a large value for the previous/next transaction ids if there are none).

I believe this sort of query can be efficiently handled in time O(k polylog n) with several data structures, like an interval tree such as a B-tree augmented with maximum values or several kinds of 2D search trees.

It's also possible to use a simple index and just reclaim those rows whose Tmax is lower than the oldest active transaction, although this means that a single never-closed transaction blocks all row reclamation forever, which seems a bad design for a production-quality database.

Re:The State of Vacuum in Postgres by rosser on Friday January 05, 2018 @05:50PM (#16082471)
...all of which structures you'd somehow need to synchronize writing to, to keep them accurate and fresh. Global write-locks do not scale, no matter how fast it might be in the toy case.
Re:The State of Vacuum in Postgres by devit on Friday January 05, 2018 @05:56PM (#16082514)
It's just an index on the transaction id fields of the rows, so it should scale like any other index on the table.
Re:The State of Vacuum in Postgres by rosser on Friday January 05, 2018 @06:07PM (#16082581)
So, basically the already-existing Visibility Map?

Indexes in postgres point to the page, not the tuple. The VM keeps two bits per page: "does this page have any 'dead' tuples?", and "does this page need to be touched for xid wraparound?"

Vacuuming doesn't touch a page unless the VM indicates it's necessary.

Re:The State of Vacuum in Postgres by rhaas on Saturday January 06, 2018 @10:33AM (#16085644)
Uh, indexes in postgres point to the tuple, not the page.

Except for BRIN.

Re:The State of Vacuum in Postgres by rosser on Saturday January 06, 2018 @04:38PM (#16087603)
Thanks for the correction, Robert! Now I'm curious where I got that notion.