4 ms·

Is it really necessary to have a vacuum procedure? Isn't it possible to just use a data structure to index rows by transaction ids, and on each transaction com

by devit 9y ago

Is it really necessary to have a vacuum procedure? Isn't it possible to just use a data structure to index rows by transaction ids, and on each transaction commit efficiently find all rows that aren't visible to any transaction, and add them to a free list? Seems kind of a bad design to rely on periodic full data scans.

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 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 ago
      It'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 ago
        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.
        rhaas 9y ago
        Uh, indexes in postgres point to the tuple, not the page. Except for BRIN.
        rosser 9y ago
        Thanks for the correction, Robert! Now I'm curious where I got that notion.
rosser 9y ago
Wouldn't a write lock on that structure become a hotly contended resource? Globally shared, globally writable structures tend not to scale very well. Postgres already has the notion of creating and destroying transaction ids for each row version attached to that tuple (row version). That distributes your "structure" across the rows involved in it. Just because you delete a row version (whether by deleting that row, or by updating it — which in MVCC is synchronously deleting the old version and inserting a new one) doesn't mean that row version isn't still visible to other concurrent activity, specifically including read-only activity. You'd therefore have to write to this proposed structure on completing every read or write.
acdha 9y ago
In general, when a respected team sticks with a design for a long time it's safe to assume it's not a bad design but that the problem is harder than it might first appear. In this case, I'd want to think carefully about the data volume: many places may have hundreds of transactions per second but also have queries which run for much longer periods of time and the visible state has to be accurate for all of them. That sounds a lot of contention for that shared data structure and “efficiently find all rows that aren't visible to any transaction” sounds decidedly non-trivial for busy servers with lots of data, which are generally the only ones where this matters.
porker 9y ago
How do other databases such as MS-SQL handle this?
- anarazel 9y ago
  Largely through undo logging.
frik 9y ago
With Postgres, SQLite and Lucene one has to always worry about VACUUM, one has to babysit the database from time to time, or write code to do so. With InnoDB engine of MySQL/MariaDB the similar OPTIMIZE TABLE command isn't needed, InnoDB runs carefree. I wouldn't want to take the database offline (write) and stop the world to do a VACUUM in production, would you?
anarazel 9y ago
> Seems kind of a bad design to rely on periodic full data scans. Note that it's not full scans - only pages that have been modified since the last vacuum, or were in a state last vacuum that they couldn't be processed, are vacuumed again. So there essentially is a block-level index for this. https://www.postgresql.org/docs/current/static/storage-vm.html https://www.postgresql.org/docs/current/static/storage-vm.ht...
jandrewrogers 9y ago
Efficient resource recovery while preserving consistency and minimally impacting workload throughput is one of THE central problems in database engine design. You can move the pain around but it never goes away, and a poor solution will very negatively impact the throughput of normal workloads. People have been thinking about this problem for as long as we've been building database engines. This is not to say vacuum-like mechanisms are necessarily the best method but it was a common architectural idiom for database engines from the 1990s because it works well with sequential storage devices. Newer techniques tend to put resource recovery inline with the workload rather than outside of it but that has other disadvantages. Indexing all rows in a database by transaction id would cause an extreme loss of throughput. That just creates a continuously mutated (and therefore locking) structure every thread constantly uses that is also paged to disk. And deletion of individual records is a problem for indexes generally.
- lobster_johnson 9y ago
  Oracle, with its undo log and some clever in-place tuple modification and space reclamation, seems to have sidestepped the issue to a much greater degree than Postgres. Oracle is MVCC-like, but sacrifices technical elegance for performance. For example, as I recall, Oracle actually writes new row data to the page the row lives in, overwriting the old data in place on commit. It also writes the modifying transaction ID to the row header. If a different transaction finds the row, it will see that the transaction ID doesn't match (it's newer than itself), which forces the database to go to the undo log to look for the older data. I'm not privy to the technical details of how the undo log is implemented or how it avoids the vacuum problem. I suspect it's related to the fact that the undo log is separate from the tuple data, so undo bloat doesn't affect table performance to the same extent as with Postgres.
  - Tostino 9y ago
    That is correct, it also means that things like rollbacks, which are pretty much instant in Postgres can take significant time in Oracle.
ketralnis 9y ago
> Seems kind of a bad design Many things can seem this way from the armchair, but you can lend some benefit of the doubt. Postgres is worked on by very smart people and it's not the only system that works this way Everything has tradeoffs.
grogers 9y ago
This is essentially what innodb does, it calls this operation "purge" as in purging dead mvcc rows, and it calls the data structure the history list (IIRC). I don't know what the exact data structure is though to find purgable rows and how it avoids contention. The main difference is that innodb runs purge in background thread(s) as opposed to blocking foreground operations. It has potential pitfalls too though. On a system with very high mutation rate, purging could fall behind. This mainly would happen if the history list overflows available buffer pool space and starts getting paged to disk (e.g. from one very long lived transection). I don't know if newer MySQL versions make purge running off disk more efficient, but 5.5 added a config for multiple purge threads.
antoaravinth 9y ago
Well this might not answer your question directly, but it shows how VACCUM solves problem such as transaction etc. Its a great video to watch, covers topic in depth : https://www.youtube.com/watch?v=ZxhBkBNxvR0 https://www.youtube.com/watch?v=ZxhBkBNxvR0

by devit 9y ago

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 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 ago
    It'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 ago
      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.
      - rhaas 9y ago
        Uh, indexes in postgres point to the tuple, not the page. Except for BRIN.
        rosser 9y ago
        Thanks for the correction, Robert! Now I'm curious where I got that notion.

rosser 9y ago

Wouldn't a write lock on that structure become a hotly contended resource? Globally shared, globally writable structures tend not to scale very well. Postgres already has the notion of creating and destroying transaction ids for each row version attached to that tuple (row version). That distributes your "structure" across the rows involved in it. Just because you delete a row version (whether by deleting that row, or by updating it — which in MVCC is synchronously deleting the old version and inserting a new one) doesn't mean that row version isn't still visible to other concurrent activity, specifically including read-only activity. You'd therefore have to write to this proposed structure on completing every read or write.

acdha 9y ago

In general, when a respected team sticks with a design for a long time it's safe to assume it's not a bad design but that the problem is harder than it might first appear. In this case, I'd want to think carefully about the data volume: many places may have hundreds of transactions per second but also have queries which run for much longer periods of time and the visible state has to be accurate for all of them. That sounds a lot of contention for that shared data structure and “efficiently find all rows that aren't visible to any transaction” sounds decidedly non-trivial for busy servers with lots of data, which are generally the only ones where this matters.

porker 9y ago

How do other databases such as MS-SQL handle this?

anarazel 9y ago
Largely through undo logging.

frik 9y ago

With Postgres, SQLite and Lucene one has to always worry about VACUUM, one has to babysit the database from time to time, or write code to do so. With InnoDB engine of MySQL/MariaDB the similar OPTIMIZE TABLE command isn't needed, InnoDB runs carefree. I wouldn't want to take the database offline (write) and stop the world to do a VACUUM in production, would you?

anarazel 9y ago

> Seems kind of a bad design to rely on periodic full data scans. Note that it's not full scans - only pages that have been modified since the last vacuum, or were in a state last vacuum that they couldn't be processed, are vacuumed again. So there essentially is a block-level index for this. https://www.postgresql.org/docs/current/static/storage-vm.html https://www.postgresql.org/docs/current/static/storage-vm.ht...

jandrewrogers 9y ago

Efficient resource recovery while preserving consistency and minimally impacting workload throughput is one of THE central problems in database engine design. You can move the pain around but it never goes away, and a poor solution will very negatively impact the throughput of normal workloads. People have been thinking about this problem for as long as we've been building database engines. This is not to say vacuum-like mechanisms are necessarily the best method but it was a common architectural idiom for database engines from the 1990s because it works well with sequential storage devices. Newer techniques tend to put resource recovery inline with the workload rather than outside of it but that has other disadvantages. Indexing all rows in a database by transaction id would cause an extreme loss of throughput. That just creates a continuously mutated (and therefore locking) structure every thread constantly uses that is also paged to disk. And deletion of individual records is a problem for indexes generally.

lobster_johnson 9y ago
Oracle, with its undo log and some clever in-place tuple modification and space reclamation, seems to have sidestepped the issue to a much greater degree than Postgres. Oracle is MVCC-like, but sacrifices technical elegance for performance. For example, as I recall, Oracle actually writes new row data to the page the row lives in, overwriting the old data in place on commit. It also writes the modifying transaction ID to the row header. If a different transaction finds the row, it will see that the transaction ID doesn't match (it's newer than itself), which forces the database to go to the undo log to look for the older data. I'm not privy to the technical details of how the undo log is implemented or how it avoids the vacuum problem. I suspect it's related to the fact that the undo log is separate from the tuple data, so undo bloat doesn't affect table performance to the same extent as with Postgres.
- Tostino 9y ago
  That is correct, it also means that things like rollbacks, which are pretty much instant in Postgres can take significant time in Oracle.

ketralnis 9y ago

> Seems kind of a bad design Many things can seem this way from the armchair, but you can lend some benefit of the doubt. Postgres is worked on by very smart people and it's not the only system that works this way Everything has tradeoffs.

grogers 9y ago

This is essentially what innodb does, it calls this operation "purge" as in purging dead mvcc rows, and it calls the data structure the history list (IIRC). I don't know what the exact data structure is though to find purgable rows and how it avoids contention. The main difference is that innodb runs purge in background thread(s) as opposed to blocking foreground operations. It has potential pitfalls too though. On a system with very high mutation rate, purging could fall behind. This mainly would happen if the history list overflows available buffer pool space and starts getting paged to disk (e.g. from one very long lived transection). I don't know if newer MySQL versions make purge running off disk more efficient, but 5.5 added a config for multiple purge threads.

antoaravinth 9y ago

Well this might not answer your question directly, but it shows how VACCUM solves problem such as transaction etc. Its a great video to watch, covers topic in depth : https://www.youtube.com/watch?v=ZxhBkBNxvR0 https://www.youtube.com/watch?v=ZxhBkBNxvR0