3 ms·
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, Tma
by devit 9y ago
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.
- 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.