Re: [PATCH 2/2] reftable: fix quadratic behavior when re-creating deleted refs

[Patrick Steinhardt <ps@pks.im>]

On Mon, Jul 06, 2026 at 01:35:56PM +0000, Kristofer Karlsson via GitGitGadget wrote:
> From: Kristofer Karlsson <krka@spotify.com>
> 
> When many refs are deleted and then re-created, update-ref exhibits
> quadratic behavior.  With 8000 refs deleted and re-created, the
> runtime is ~15s, quadrupling for each doubling of input size.
> 
> The root cause is the merged iterator's suppress_deletions flag.
> When set, merged_iter_next_void() silently consumes tombstone records
> in a tight internal loop before returning to the caller.  This
> prevents higher-level code from checking iteration bounds (such as
> prefix or refname comparisons) until after all tombstones have been
> scanned.
> 
> This affects two code paths during ref creation:
> 
>  - refs_verify_refnames_available() seeks to "refs/tags/foo-1/" to
>    check for D/F conflicts and must scan through all subsequent
>    tombstones before the caller can see that they are past the prefix
>    of interest.
> 
>  - reftable_backend_read_ref() seeks to a specific refname and must
>    scan through all subsequent tombstones before returning "not
>    found", because the merged iterator skips the matching tombstone
>    and searches for the next live record.

It probably not only impacts reference creation, but also every reader
that wants to search for a specific reference that doesn't exist.

> Fix this by removing suppress_deletions from the merged iterator and
> instead handling deletion records at each call site in the reftable
> backend, where prefix and refname bounds are available.  Tombstones
> are now returned to callers, which skip them after their existing
> bounds checks.  This allows iteration to terminate as soon as a
> tombstone past the relevant bound is encountered.

This option is still used by downstream users of the reftable library,
like libgit2. So we shouldn't just delete it outright.

> diff --git a/refs/reftable-backend.c b/refs/reftable-backend.c
> index 4ae22922de..8c4f119ff1 100644
> --- a/refs/reftable-backend.c
> +++ b/refs/reftable-backend.c
> @@ -633,6 +633,9 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator)
>  			break;
>  		}
>  
> +		if (iter->ref.value_type == REFTABLE_REF_DELETION)
> +			continue;
> +
>  		if (iter->exclude_patterns && should_exclude_current_ref(iter))
>  			continue;
>  

Okay. I was first wondering whether we should move this call earlier.
But we actually don't want to, as this is the code that precedes the
above:

	if (iter->prefix_len &&
	    strncmp(iter->prefix, iter->ref.refname, iter->prefix_len)) {
		iter->err = 1;
		break;
	}

So this allows us to not only skip the current iteration, but completely
abort iteration by observing tombstones that sort after our prefix.

In any case, as far as I can see all sites where we iterate through
either ref or log records have been adapted to handle deletions.

Thanks!

Patrick