News for hackers. Stuff that matters.
Re:The State of Vacuum in Postgres by al_james on Friday January 05, 2018 @04:58PM (#16082090)
Sadly it's a bit more complex than that. Because currently running different transactions may hold a view of the database as it was before the transaction commits, the actual view of what does can be reclaimed depends on what transactions are currently active. Thus upon commit, it may be that some tuples release by the committed transaction are still visible to others.

Vacuum actually works by looking for tuples where no running transactions can see them anymore. Postgres, in effect, maintains a minimum and maximum transaction ID that any tuple is visible for, and vacuum scans over all of those that have a max visible transaction ID (suggesting it's available to be reclaimed) and which is less than the minimum active transaction ID.

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.