Re: UNDO with constant time recovery (CTR)

On Monday, October 5th, 2026 at 5:23 PM, Matthias van de Meent <boekewurm+postgres(at)gmail(dot)com> wrote:

> 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.

It's how PG works if the table AM is keeping MVCC versions in the pages
that make up the table rather than in the WAL log. That might be how
SQLServer does it, but my demo FLUX table AM doesn't and it may never
show promise as a viable table AM for production load but that's TBD
at this point.

> 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).

Yes, time bounded based on checkpoint distance and the per-backend WAL
log that is used by FLUX is that "side stream of UNDO operations".

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

Agreed, and it's exciting to be trying out a different set of
trade-offs than HEAP presents us. I went into this thinking I was
going to "fix" HEAP, now I admire the careful trade-offs HEAP makes.

UNDO isn't either or, it's both. Some people need the trade-offs
that an in-place update table AM that uses UNDO for MVCC, others
don't. Today that door isn't available, I'm just proposing that
there is value in installing the door. You choose which one you
want.

> 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.

Yes, and it is a bit of a marketing leap to use those words. I think
I admitted that in my first reply earlier on. :)

> 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.

Yes, and no. Here is where I think I've diverged a bit from SQLServer,
their MVCC cleanup tasks are similar to autovacuum but they need that so
they can do in-page MVCC chains like HEAP does. I'm not doing that with
FLUX, I'm using the WAL for reconstructing tuples when necessary.

Yes, this setup is n-WAL logs where there is one common one and then one
per-backend for the FLUX table. That adds I/O and s_b pressure and does
end up writing more than HEAP does (aka "bloat") when you measure that.

As you deftly point out, there's no magic beans. UNDO is just different
trade-offs. For FLUX with UNDO you don't have to vacuum, except that you
do need to analyze occasionally and you do have to tend to the creation
and removal of the per-backend WAL files. So, no it's not free.

The fun part is in the exploration and discovery of a) why HEAP has stood
the test of time, b) where it has been baked into other parts of the
system too deeply, c) how might the trade-offs be rearranged and would
anyone care?

I appreciate the conversation and time you've given to this and I hope
you continue to chime in. Maybe we'll find a dead-end, or maybe we'll
learn something and open a door that enables a new class of use cases
for Postgres. Does that make sense?

> Kind regards,
>
> Matthias van de Meent
> Databricks (https://www.databricks.com)

I'm not promising a miracle, just UNDO. That may be too much or not
enough and I'm okay with that too.

-greg