Thread

1. PoC: Compute a histogram of prune_xid to support autovacuum improvements

   Renan Alves Fonseca <renanfonseca@gmail.com> — 2025-06-03T16:39:44Z

   Hi all,
   
   in the scope of improving the autovacuum algorithm, this patch proposes
   to maintain a histogram of *smallest prunable xid per page* for each
   relation. It allows to estimate the number of pages that would
   be pruned by vacuum for a given cutoff.
   
   The *smallest prunable xid per page* is prune_xid in each page
   header. The value of prune_xid is not always consistent with the
   contents of the page, but this patch does not try to improve on this. We
   suppose that the current accuracy of prune_xid is good enough.
   
   The histogram lives in PgStat_StatTabEntry, and so it makes use of
   pgstat machinery. In particular, there is a per-backend transient
   histogram that is merged into the main shared histogram using
   pgstat_report_vacuum() or pgstat_relation_flush_cb().
   
   This histogram uses a fixed size data structure but its bounds are
   dynamic. Over time, some bins are merged to give space for a fresh new
   bin that covers the ever increasing xids. The maintenance of the
   histogram bounds is a relatively expensive operation, whereas a simple
   update of the bins count is very efficient. So, we may arrange to do the
   expensive operation out of the hot paths.
   
   In order to collect data, we keep track of prune_xid in (1) access heap
   prune, (2) vacuum and (3) heap_{delete,update,insert}. Adding stuff in
   (3) might raise eyebrows since it is a cost per tuple. However, we only
   do something if the page prune_xid changes and, finally, it is virtually
   a cost per page.
   
   You can give a try using pgbench like this.
   ``` shell
   pgbench -i
   pgbench -T 30
   ```
   
   ``` psql
   \set tt pgbench_accounts
   \i src/test/regress/sql/prune_xid_aux_check.sql
   ```
   
   The functions pg_stat_get_prune_xid_{freqs,bounds} return the prune_xid
   histogram for a given relation. In the second part of the script above,
   we use *pageinspect* to check the correctness of the computed
   histogram. In my tests, not always, a small annoying difference shows
   up. Actually, it is really annoying, I'm struggling with it and I hope
   someone helps me to find the missing bits.
   
   Regarding performance, I've not observed a sensible difference using
   pgbench but I certainly don't have a good setup for benchmarking. I
   could observe, using *perf*, that the function
   pgstat_update_relation_prune_xid_histogram(), which collects data in
   almost all cases, has a overall time much lower than
   pgstat_count_heap_update() for example. I've looked at perf data using
   pgbench and using huge batch updates.
   
   The initial version of this work proposed a histogram of dead tuples
   xmax for each relation. After some suggestions in the discord hackers
   channel, I've understood that a page wise info can be more useful for
   the autovacuum planning. There is more detailed information in the file
   patch-notes.{org,md} and, of course, in the code itself.
   
   The attached patch is based on REL_18_BETA1. Sorry for not sending a
   complete, rounded patch. But I feel that I really need some feedback at
   this point. Above all, I'd like to know if someone is interested in
   using this information to improve the autovacuum algorithm. Otherwise,
   we cannot justify this patch.
   
   Looking forward to any kind of feedback.
   
   Best Regards,
   Renan Fonseca
   
   

2. Re: PoC: Compute a histogram of prune_xid to support autovacuum improvements

   Renan Alves Fonseca <renanfonseca@gmail.com> — 2025-06-05T00:33:09Z

   Renan Alves Fonseca <renanfonseca@gmail.com> writes:
   
   > histogram. In my tests, not always, a small annoying difference shows
   > up. Actually, it is really annoying, I'm struggling with it and I hope
   > someone helps me to find the missing bits.
   
   Finally, I've found out that this error has been triggered by my test
   script. The problem arises when we run an ANALYZE command and there are
   pending stats waiting to be flushed. It seems that the pending stats are
   completely discarded, which might make sense for other statistics.
   
   Besides that, the patch works as expected.
   
   
   
   

3. Re: PoC: Compute a histogram of prune_xid to support autovacuum improvements

   Melanie Plageman <melanieplageman@gmail.com> — 2025-12-09T20:21:15Z

   On Tue, Jun 3, 2025 at 12:40 PM Renan Alves Fonseca
   <renanfonseca@gmail.com> wrote:
   >
   > in the scope of improving the autovacuum algorithm, this patch proposes
   > to maintain a histogram of *smallest prunable xid per page* for each
   > relation. It allows to estimate the number of pages that would
   > be pruned by vacuum for a given cutoff.
   
   Thanks for working on this, Renan.
   
   It is quite a large patch set, which makes sense because we do not
   have histogram types in any of the shared memory stats right now. I
   think if we want to go the route of adding a histogram, we might want
   to make it general purpose enough to use for other types of stats. In
   fact there is nothing about your PruneXidHistogram struct which has to
   be related to prune xids.
   
   Before doing that, I was wondering if there was a way to make
   incremental progress by adding and maintaining the oldest prune xid.
   It would mean adding code in the same places (heap_update/delete/etc).
   In heap_page_prune_and_freeze(), we would have to keep track of the
   oldest new prune xid given that we will probably be pruning away the
   previous oldest one.
   
   Then when vacuuming, we could consider skipping vacuuming the relation
   if the oldest prunable xid is newer than OldestXmin (unless we thought
   we'd be able to freeze tuples).
   
   I know your patch doesn't use the histograms now in vacuum decisions
   (only displays them). But maybe it is worth approaching from the
   opposite direction and use a coarser heuristic first and then make it
   more detailed.
   
   - Melanie
   
   
   
   

4. Re: PoC: Compute a histogram of prune_xid to support autovacuum improvements

   Renan Alves Fonseca <renanfonseca@gmail.com> — 2025-12-10T17:25:06Z

   Melanie Plageman <melanieplageman@gmail.com> writes:
   >
   > Thanks for working on this, Renan.
   >
   Thanks for the feedback.
   
   > It is quite a large patch set, which makes sense because we do not
   > have histogram types in any of the shared memory stats right now. I
   > think if we want to go the route of adding a histogram, we might want
   > to make it general purpose enough to use for other types of stats. In
   > fact there is nothing about your PruneXidHistogram struct which has to
   > be related to prune xids.
   >
   True.
   
   > Before doing that, I was wondering if there was a way to make
   > incremental progress by adding and maintaining the oldest prune xid.
   > It would mean adding code in the same places (heap_update/delete/etc).
   > In heap_page_prune_and_freeze(), we would have to keep track of the
   > oldest new prune xid given that we will probably be pruning away the
   > previous oldest one.
   In order to keep track of the oldest prune xid we need to keep some
   info about all prune xid in the relation. Note that there can be more
   than one page with same prune xid. So if we look only at a local prune
   (which is the info that we have at those places), we cannot update the
   global oldest prune xid, unless we know that it matches the current
   oldest AND the current oldest occurs only once. Besides that, we cannot
   say that the new prune xid of current page is the new oldest one
   (probably it isn't).
   
   Actually the main objective of maintaining this histogram is to keep
   track of the relation oldest prunable xid in a concise manner. The
   bounds of the first bin are the most important. The other bins are there
   just to support this information in the future as the histogram gets
   updated. The fact that we can eventually use this information in a
   complex heuristic is just a bonus.
   
   The information that we need to precisely keep track of the oldest prune
   xid would be better modeled by a counter/multiset/bag containing
   pages prune xid of a given relation. I discarded this approach
   because it seemed hard to integrate such a complex data structure in
   pg stat system (but that may be reviewed). The histogram approach
   is actually an approximation of the info that would be represented by
   this multiset. The advantage of this implementation is that it uses a
   fixed size data structure that can be integrated in pg stat system.  
   
   >
   > Then when vacuuming, we could consider skipping vacuuming the relation
   > if the oldest prunable xid is newer than OldestXmin (unless we thought
   > we'd be able to freeze tuples).
   >
   Then, if we really don't care about the additional information regarding
   higher page prune xid, there is another way to keep track of the oldest
   prunable xid of the relation: maintain a histogram of tuples xid
   (max_xid, right?) instead of pages prune_xid. The advantage is that we
   don't need to touch heap_{update,insert,delete} functions. In this
   configuration, the penalty of maintaining the histogram would be
   per-transaction and not per-page.
   
   > I know your patch doesn't use the histograms now in vacuum decisions
   > (only displays them). But maybe it is worth approaching from the
   > opposite direction and use a coarser heuristic first and then make it
   > more detailed.
   
   Unfortunately, I don't see how to make this part even more simple. But your
   suggestion of creating a simple heuristic based only on the oldest
   prunable xid could fit in this patch, at least for evaluation
   purposes. So from this point, the options are:
   
   1. Go ahead with this, implementing the vacuum skip.
   
   2. Switch to tuple-wise histogram to avoid performance issues. Then,
   implement same vacuum skip.
   
   3. Abandon this path and look for a more complete solution. We would use
   a more complex data structure like a multiset or even an array
   containing prune_xid's of each page. This data structure would not live
   in pg stat, and would have a life cycle similar to a visibility map. The
   detailed information would eventually allow the vacuum to skip pages
   BEFORE fetching them. Well, I would need help...
   
   Best regards,
   Renan Fonseca