Re: UNDO with constant time recovery (CTR)

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

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

best.

-greg

[1] https://www.microsoft.com/en-us/research/wp-content/uploads/2019/06/p700-antonopoulos.pdf
[2] https://www.vldb.org/pvldb/vol19/p3916-gandikota.pdf