Re: [PATCH v3 2/2] reftable: fix quadratic behavior in the presence of tombstones
On Fri, Jul 10, 2026 at 10:36:07AM +0000, Kristofer Karlsson via GitGitGadget wrote:
Show 40 quoted lines
> 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.
Show 11 quoted lines
> 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.
Show 11 quoted lines
> 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