4 ms·
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 comm
by al_james 9y ago
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.
- devit 9y agoSure, 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.
- rosser 9y ago...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.
- devit 9y agoIt's just an index on the transaction id fields of the rows, so it should scale like any other index on the table.
- rosser 9y agoSo, 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.