Re: [PATCH v3 2/2] reftable: fix quadratic behavior in the presence of tombstones

[Patrick Steinhardt <ps@pks.im>]

On Fri, Jul 10, 2026 at 10:36:07AM +0000, Kristofer Karlsson via GitGitGadget wrote:
> From: Kristofer Karlsson <krka@spotify.com>
> 
> When many tombstones are present in a reftable, operations that need
> to look up or iterate over refs exhibit quadratic behavior.  With
> 8000 refs deleted and re-created, update-ref takes ~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 any code path that seeks into a range containing
> tombstones, including:
> 
>  - 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.
> 
> Fix this by making suppress_deletions configurable via
> reftable_stack_options instead of unconditionally enabling it.  Git
> no longer sets the flag, so tombstones are now returned to callers in
> the reftable backend, which skip them after their existing bounds
> checks.  This allows iteration to terminate as soon as a tombstone
> past the relevant bound is encountered.
> 
> Downstream users of the reftable library (e.g. libgit2) can still
> enable suppress_deletions through the stack options to retain the
> previous behavior.
> 
> This also requires adding deletion checks to the log iteration paths,
> since suppress_deletions applied to both ref and log iterators.

Nit: s/applied/applies/

> diff --git a/reftable/reftable-stack.h b/reftable/reftable-stack.h
> index 11f9963f4f..5d22d84e80 100644
> --- a/reftable/reftable-stack.h
> +++ b/reftable/reftable-stack.h
> @@ -42,6 +42,8 @@ struct reftable_stack_options {
>  	 */
>  	void (*on_reload)(void *payload);
>  	void *on_reload_payload;
> +
> +	int suppress_deletions;
>  };

A comment would've been nice, but I don't think this warrants a reroll.

> diff --git a/reftable/stack.c b/reftable/stack.c
> index ab12926708..caaedf24d6 100644
> --- a/reftable/stack.c
> +++ b/reftable/stack.c
> @@ -337,7 +337,7 @@ static int reftable_stack_reload_once(struct reftable_stack *st,
>  	/* Update the stack to point to the new tables. */
>  	if (st->merged)
>  		reftable_merged_table_free(st->merged);
> -	new_merged->suppress_deletions = 1;
> +	new_merged->suppress_deletions = st->opts.suppress_deletions;
>  	st->merged = new_merged;

Yup, this looks good to me.

Thanks!

Patrick