Re: UNDO with constant time recovery (CTR)

On Mon, 5 Oct 2026 at 21:49, Greg Burd <greg(at)burd(dot)me> wrote:
>
>
> > On Oct 5, 2026, at 6:59 AM, Matthias van de Meent <boekewurm+postgres(at)gmail(dot)com> wrote:
> >
> > On Tue, 29 Sept 2026, 00:29 Greg Burd, <greg(at)burd(dot)me> wrote:
> >>
> >> Hello hackers,
> >>
> >
> > Hi Greg,
>
> Hello Matthias, thanks for taking the time to review.
>
> > A few things popped out in this thread, so here's a few comments.
> >
> > [...]
> >
> >> All these authors and more deserve credit for their hard work, thank
> >> you. In the case of ZHeap and Zedstore the ultimate goal was a new table
> >> AM. I'm not going to boil that ocean up front, here is where I'm going
> >> to diverge from those past projects.
> >
> > I'd prefer if you didn't boil any oceans in the process of making
> > contributions. Not up front is a good start, but please don't do that
> > later on, either.
>
> Ha! Yeah, oceans are not to be boiled. Noted. But really what I was
> saying is that although I'd included FLUX the intent of this series was
> to focus on UNDO and FILEOPS and keep HEAP out of it. Changes to index
> AMs are essentially no-ops in preparation for a future where a table AM
> based on UNDO could exist, so arguably they should wait for later too.
>
> > [...]
> >
> >> If a transaction is in flight and creates a new file and then crashes to
> >> me it makes sense that after recovery that new file is gone and the
> >> system is consistent again.
> >
> > That very much depends on the type of file created. E.g. WAL files,
> > SLRU files, and new segments of existing relations should not be
> > removed just because they were created by a transaction that crashed
> > or rolled back -- other backends may have have written to those files.
>
> Yes, there are exceptions and I should list them. WAL-logging an undo
> record for a WAL log change is nuts, never going to work.
>
> > Also note that we may want to have UNDO outside transactional
> > boundaries: after all, not all DDL is transactional, and I think
> > there's some gain to be had for e.g. REINDEX CONCURRENTLY; it allows
> > us to truncate the !indisready index files it leaves behind after a
> > crash, reducing disk bloat in those cases.
>
> Hmmm... I'll have to wrap my head around this one. UNDO outside of
> a transaction isn't something I'd sign up for, why not just wrap
> these changes in transactions? I get the DDL issue, the reindex
> one sounds like a good idea. I'll dig a bit, thanks for opening the
> door on this.
>
> > Side note: I'd prefer if this change does _not_ mean that unlogged
> > relations get to WAL-log proportional to data operations. Undo
> > logging can be useful, but should not be predicated on WAL if a
> > tableAM requires UNDO.
>
> Good point, I'll need to recheck that I indeed disable UNDO when
> the relation is unlogged...
>
> > [...]
> >
> >> Also, I realize that this kind of change takes a lot of time to gain
> >> traction and adoption into core, if at all. I'm ready for that, sure
> >> we're working on v20 now and v19 is inching out the door maybe this
> >> merges into v25 or maybe it gets shelved along the way for good reason.
> >> Who knows, but I do know that it's worth the effort to advocate and to
> >> have a durable record for others interested in it even if it doesn't get
> >> merged in this time. I look forward to seeing what happens. :)
> >
> > The title indicates constant-time recovery, but I don't see anything
> > in this thread that supports this claim. Could you expand on the
> > mechanisms you're using to guarantee this?
>
> Yes, the target is [1] and possibly [2]. The technique boils down to
> keeping an "aborted transaction map" (ATM) that you can build during
> the recovery process which prevents the need for replaying the UNDO
> records at recovery time to restore physical page information and
> leaves that for a background worker.
>
> > I also don't see how your claimed constant-time rollback can work,
> > given that the size of a transaction's modified working set is bounded
> > only by time and the space available to store the database, and that
> > undoing changes in files can't really be done faster than the
> > bandwidth of your CPU. Undoing a set of transaction operations
> > therefore can't really be constant-time unless you're limiting the
> > number of undo-able transaction operations, and a limited transaction
> > size is not really something current users have to consider (and thus,
> > don't expect).
>
> Take a look at the papers, I'll fix up the code and docs and wiki.
> I'll check back with you on the next patch update and see if I
> managed to clear this concept up or not. :)

So, IIUC, the "CTR" here practically means:

We use a small checkpoint interval for WAL-logged MVCC-versioned
REDO-able operations that don't need an online UNDO phase (this is how
PG works), and store rare UNDO operations in a side stream.
Then we claim that the checkpoint REDO window is time-bounded
(which is true, but with checkpoint distance -dependent bounds), and
also claim that the side stream of UNDO operations is also bounded
(without showing a proof on this).

I'll have to quote Dodgeball on that: "It's a bold strategy, Cotton.
Let's see if it pays off for him."

And, indeed, the paper's metrics show that "constant time recovery"
still means "60 seconds of recovery at p99; 180 seconds recovery at
p99.99", which is a much larger difference than one should expect from
something that claims to be constant time.

Aside: The paper's claimed recovery time also explicitly does not
cover the time spent in their equivalent of an autovacuum worker,
which is tasked with running MVCC cleanup tasks for transactions that
are in their final state and created dead MVCC version in the table.
This is OK in principle, but its existence does seem like a critical
conflict for buidling tableAMs relying on this paper whilst claiming
that "it does not need vacuum". Because this paper seems to heavily
depend on a background task that does VACUUM's job of cleaning up old
MVCC versions to avoid pushing operations onto the UNDO work queue.

Kind regards,

Matthias van de Meent
Databricks (https://www.databricks.com)