Re: UNDO with constant time recovery (CTR)

On Tue, 6 Oct 2026 at 03:58, Greg Burd <greg(at)burd(dot)me> wrote:
>
>
>
> 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.

If your FLUX table doesn't, then it doesn't follow CTR, so using the
paper's name will only lead to confuse readers.

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

But that side stream is not limited in any way I can see.

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

I'm all for installing doors to rooms that need more doors, but let's
first take a look at whether the wall you're installing it into is
load-bearing before you start deconstructing it to make space for the
door, or bulldoze the whole house because you think the best place to
put the door is where the hearth currently is located.

> > 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'd expected that we didn't use papers based on their marketing
claims, but on their true merits. If you take the constant-time
recovery out of CTR you're not left with much, if anything.

> I think
> I admitted that in my first reply earlier on. :)

Hmm, maybe it was my then-tired mind not picking up on it, because it
wasn't clear to me. I really dislike marketing claims that can't be
backed by hard numbers.

> > 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 fairly sure they need it so they can get rid of rolled back
transactions and other detritis produced by MVCC, regardless of the
MVCC storage approach. Heck, even MySQL has maintenance workers for
this.

> I'm not doing that with
> FLUX, I'm using the WAL for reconstructing tuples when necessary.

That's going to cause issues with retention of MVCC data. Right now,
we only need up to two times max_wal_size, and even then users find a
way to drop the contents of the pg_wal directory.

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

If not with vacuum, how do you recover from e.g. transaction rollback,
or lost connections?

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

Please allow me to find fun in different things.

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

Maybe. But I don't think the -hackers list is a good place to
prototype changes many layers deep, with new MB-sized patches every
day, without that thread explictly describing the status of the
patchset as experimental. Having an end goal in mind is great, but I
can't (and won't) review MB-sized patchsets that do too many things at
once, at least not to the detail that would be required for it to get
committed. FYI, based on the patch headers, I think this patchset is
trying to do too much at once by a factor of _at least_ 3.

Kind regards,

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