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

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

[Kristofer Karlsson via GitGitGadget]

This series fixes quadratic behavior in update-ref when many refs are
deleted (tombstoned) and then new refs are created with the reftable
backend.

The root cause is the merged iterator's suppress_deletions flag, which
silently consumes tombstone records in a tight internal loop. This prevents
higher-level code from checking iteration bounds until after all tombstones
have been scanned, making both refs_verify_refnames_available() and
reftable_backend_read_ref() O(n) per call in the presence of tombstones.

The fix removes suppress_deletions from the merged iterator and instead
handles deletion records at each call site in the reftable backend, where
prefix and refname bounds are available. This lets existing bounds checks
terminate iteration early when encountering tombstones past the relevant
bound.

The first patch adds tests for tombstone scenarios: a perf test (p1401)
exercising two patterns with 8000 refs, and a correctness test (t0610)
verifying that deleted-then-recreated refs are visible.

The second patch is the pure optimization. Both p1401 tests go from ~14s to
~0.2s with the fix.

Note that auto-compaction typically merges tombstones before they accumulate
to this degree, so the quadratic behavior may not show up in every workflow.
But the fix ensures correct time complexity regardless of compaction state,
and the change is fairly contained.

Previous discussion:
https://lore.kernel.org/git/20260701080014.GA3748390@coredump.intra.peff.net/

Kristofer Karlsson (2):
  t: add tests for ref tombstone scenarios
  reftable: fix quadratic behavior when re-creating deleted refs

 refs/reftable-backend.c              | 54 ++++++++++++++++++++++------
 reftable/merged.c                    | 12 +------
 reftable/merged.h                    |  4 ---
 reftable/stack.c                     |  1 -
 t/perf/p1401-ref-store-tombstones.sh | 44 +++++++++++++++++++++++
 t/t0610-reftable-basics.sh           | 22 ++++++++++++
 6 files changed, 110 insertions(+), 27 deletions(-)
 create mode 100755 t/perf/p1401-ref-store-tombstones.sh


base-commit: e9019fcafe0040228b8631c30f97ae1adb61bcdc
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2166%2Fspkrka%2Freftable-tombstone-perf-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2166/spkrka/reftable-tombstone-perf-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/2166
-- 
gitgitgadget

[PATCH 1/2] t: add tests for ref tombstone scenarios

[Kristofer Karlsson via GitGitGadget]

From: Kristofer Karlsson <krka@spotify.com>

Add a performance test and a correctness test for update-ref when
many tombstones are present in a reftable.

The performance test (p1401) exercises two scenarios:

 - All refs are deleted (creating tombstones) and then re-created
   with the same names, which currently exhibits quadratic behavior.

 - An asymmetric variant where refs are deleted and then new,
   differently-named refs are created.  When the tombstones sort
   after the new refs, every create scans all tombstones, making
   this case even worse than re-creating the same refs.

The correctness test (t0610) verifies that refs deleted and then
re-created with the same names are visible afterwards.

Helped-by: Jeff King <peff@peff.net>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 t/perf/p1401-ref-store-tombstones.sh | 44 ++++++++++++++++++++++++++++
 t/t0610-reftable-basics.sh           | 22 ++++++++++++++
 2 files changed, 66 insertions(+)
 create mode 100755 t/perf/p1401-ref-store-tombstones.sh

diff --git a/t/perf/p1401-ref-store-tombstones.sh b/t/perf/p1401-ref-store-tombstones.sh
new file mode 100755
index 0000000000..e40a6dcbf4
--- /dev/null
+++ b/t/perf/p1401-ref-store-tombstones.sh
@@ -0,0 +1,44 @@
+#!/bin/sh
+
+test_description="Tests performance of ref operations with many tombstones"
+
+. ./perf-lib.sh
+
+test_expect_success "setup" '
+	git init --ref-format=reftable repo &&
+	blob=$(echo foo | git -C repo hash-object -w --stdin) &&
+	for i in $(test_seq 8000)
+	do
+		printf "create refs/tags/tag-%d %s\n" "$i" "$blob" ||
+		return 1
+	done >repo/input &&
+	git -C repo update-ref --stdin <repo/input &&
+	git -C repo for-each-ref --format="delete %(refname)" |
+	git -C repo update-ref --stdin
+'
+
+test_perf "recreate refs after mass delete" '
+	git -C repo update-ref --stdin <repo/input &&
+	git -C repo for-each-ref --format="delete %(refname)" |
+	git -C repo update-ref --stdin
+'
+
+test_expect_success "setup asymmetric" '
+	for i in $(test_seq 8000)
+	do
+		printf "create refs/tags/old-%d %s\n" "$i" "$blob" ||
+		return 1
+	done >repo/input-old &&
+	sed "s/old-/new-/" <repo/input-old >repo/input-new &&
+	git -C repo update-ref --stdin <repo/input-old &&
+	git -C repo for-each-ref --format="delete %(refname)" |
+	git -C repo update-ref --stdin
+'
+
+test_perf "create new refs after deleting differently-named refs" '
+	git -C repo update-ref --stdin <repo/input-new &&
+	git -C repo for-each-ref --format="delete %(refname)" |
+	git -C repo update-ref --stdin
+'
+
+test_done
diff --git a/t/t0610-reftable-basics.sh b/t/t0610-reftable-basics.sh
index e19e036898..4b7cfe38e4 100755
--- a/t/t0610-reftable-basics.sh
+++ b/t/t0610-reftable-basics.sh
@@ -1163,4 +1163,26 @@ test_expect_success 'writes do not persist peeled value for invalid tags' '
 	)
 '
 
+test_expect_success 'delete and re-create refs with tombstones' '
+	test_when_finished "rm -rf repo" &&
+	git init repo &&
+	test_commit -C repo A &&
+	A=$(git -C repo rev-parse HEAD) &&
+	cat >input <<-EOF &&
+	create refs/tags/a $A
+	create refs/tags/b $A
+	create refs/tags/c $A
+	EOF
+	git -C repo update-ref --stdin <input &&
+
+	# delete all tags, leaving tombstones
+	git -C repo for-each-ref --format="delete %(refname)" refs/tags/ |
+	git -C repo update-ref --stdin &&
+
+	# re-create the same refs and verify they are visible
+	git -C repo update-ref --stdin <input &&
+	git -C repo tag -l >actual &&
+	test_line_count = 3 actual
+'
+
 test_done
-- 
gitgitgadget

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

[Kristofer Karlsson via GitGitGadget]

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.

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 also requires adding deletion checks to the log iteration paths,
since suppress_deletions applied to both ref and log iterators.

Both tests in p1401 go from ~14s to ~0.2s with this change.

Reported-by: Jeff King <peff@peff.net>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 refs/reftable-backend.c | 54 ++++++++++++++++++++++++++++++++---------
 reftable/merged.c       | 12 +--------
 reftable/merged.h       |  4 ---
 reftable/stack.c        |  1 -
 4 files changed, 44 insertions(+), 27 deletions(-)

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
@@ -86,7 +86,8 @@ static int reftable_backend_read_ref(struct reftable_backend *be,
 	if (ret)
 		goto done;
 
-	if (strcmp(ref.refname, refname)) {
+	if (strcmp(ref.refname, refname) ||
+	    reftable_ref_record_is_deletion(&ref)) {
 		ret = 1;
 		goto done;
 	}
@@ -112,7 +113,6 @@ static int reftable_backend_read_ref(struct reftable_backend *be,
 		oidread(oid, reftable_ref_record_val1(&ref),
 			&hash_algos[hash_id]);
 	} else {
-		/* We got a tombstone, which should not happen. */
 		BUG("unhandled reference value type %d", ref.value_type);
 	}
 
@@ -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;
 
@@ -1492,6 +1495,8 @@ static int write_transaction_table(struct reftable_writer *writer, void *cb_data
 					ret = 0;
 					break;
 				}
+				if (reftable_log_record_is_deletion(&log))
+					continue;
 
 				ALLOC_GROW(logs, logs_nr + 1, logs_alloc);
 				tombstone = &logs[logs_nr++];
@@ -1889,6 +1894,8 @@ static int write_copy_table(struct reftable_writer *writer, void *cb_data)
 			ret = 0;
 			break;
 		}
+		if (reftable_log_record_is_deletion(&old_log))
+			continue;
 
 		free(old_log.refname);
 
@@ -2019,6 +2026,9 @@ static int reftable_reflog_iterator_advance(struct ref_iterator *ref_iterator)
 		if (iter->err)
 			break;
 
+		if (reftable_log_record_is_deletion(&iter->log))
+			continue;
+
 		/*
 		 * We want the refnames that we have reflogs for, so we skip if
 		 * we've already produced this name. This could be faster by
@@ -2178,6 +2188,8 @@ static int reftable_be_for_each_reflog_ent_reverse(struct ref_store *ref_store,
 			ret = 0;
 			break;
 		}
+		if (reftable_log_record_is_deletion(&log))
+			continue;
 
 		ret = yield_log_record(refs, &log, fn, cb_data);
 		if (ret)
@@ -2230,6 +2242,10 @@ static int reftable_be_for_each_reflog_ent(struct ref_store *ref_store,
 			ret = 0;
 			break;
 		}
+		if (reftable_log_record_is_deletion(&log)) {
+			reftable_log_record_release(&log);
+			continue;
+		}
 
 		ALLOC_GROW(logs, logs_nr + 1, logs_alloc);
 		logs[logs_nr++] = log;
@@ -2276,18 +2292,26 @@ static int reftable_be_reflog_exists(struct ref_store *ref_store,
 		goto done;
 
 	/*
-	 * Check whether we get at least one log record for the given ref name.
-	 * If so, the reflog exists, otherwise it doesn't.
+	 * Check whether we get at least one non-deleted log record for the
+	 * given ref name.  If so, the reflog exists, otherwise it doesn't.
 	 */
-	ret = reftable_iterator_next_log(&it, &log);
-	if (ret < 0)
-		goto done;
-	if (ret > 0) {
-		ret = 0;
-		goto done;
+	while (1) {
+		ret = reftable_iterator_next_log(&it, &log);
+		if (ret < 0)
+			goto done;
+		if (ret > 0) {
+			ret = 0;
+			goto done;
+		}
+		if (strcmp(log.refname, refname)) {
+			ret = 0;
+			goto done;
+		}
+		if (!reftable_log_record_is_deletion(&log))
+			break;
 	}
 
-	ret = strcmp(log.refname, refname) == 0;
+	ret = 1;
 
 done:
 	reftable_iterator_destroy(&it);
@@ -2399,6 +2423,8 @@ static int write_reflog_delete_table(struct reftable_writer *writer, void *cb_da
 			ret = 0;
 			break;
 		}
+		if (reftable_log_record_is_deletion(&log))
+			continue;
 
 		tombstone.refname = (char *)arg->refname;
 		tombstone.value_type = REFTABLE_LOG_DELETION;
@@ -2580,6 +2606,10 @@ static int reftable_be_reflog_expire(struct ref_store *ref_store,
 			reftable_log_record_release(&log);
 			break;
 		}
+		if (reftable_log_record_is_deletion(&log)) {
+			reftable_log_record_release(&log);
+			continue;
+		}
 
 		oidread(&old_oid, log.value.update.old_hash,
 			ref_store->repo->hash_algo);
@@ -2746,6 +2776,8 @@ static int reftable_be_fsck(struct ref_store *ref_store, struct fsck_options *o,
 		report.path = refname.buf;
 
 		switch (ref.value_type) {
+		case REFTABLE_REF_DELETION:
+			continue;
 		case REFTABLE_REF_VAL1:
 		case REFTABLE_REF_VAL2: {
 			struct object_id oid;
diff --git a/reftable/merged.c b/reftable/merged.c
index 733de07454..2f9a361234 100644
--- a/reftable/merged.c
+++ b/reftable/merged.c
@@ -26,7 +26,6 @@ struct merged_iter {
 	struct merged_subiter *subiters;
 	struct merged_iter_pqueue pq;
 	size_t subiters_len;
-	int suppress_deletions;
 	ssize_t advance_index;
 };
 
@@ -166,15 +165,7 @@ static int merged_iter_seek_void(void *it, struct reftable_record *want)
 
 static int merged_iter_next_void(void *p, struct reftable_record *rec)
 {
-	struct merged_iter *mi = p;
-	while (1) {
-		int err = merged_iter_next_entry(mi, rec);
-		if (err)
-			return err;
-		if (mi->suppress_deletions && reftable_record_is_deletion(rec))
-			continue;
-		return 0;
-	}
+	return merged_iter_next_entry(p, rec);
 }
 
 static struct reftable_iterator_vtable merged_iter_vtable = {
@@ -278,7 +269,6 @@ int merged_table_init_iter(struct reftable_merged_table *mt,
 		goto out;
 	}
 	mi->advance_index = -1;
-	mi->suppress_deletions = mt->suppress_deletions;
 	mi->subiters = subiters;
 	mi->subiters_len = mt->tables_len;
 
diff --git a/reftable/merged.h b/reftable/merged.h
index 4317e5f5f6..6fafd1d080 100644
--- a/reftable/merged.h
+++ b/reftable/merged.h
@@ -17,10 +17,6 @@ struct reftable_merged_table {
 	size_t tables_len;
 	enum reftable_hash hash_id;
 
-	/* If unset, produce deletions. This is useful for compaction. For the
-	 * full stack, deletions should be produced. */
-	int suppress_deletions;
-
 	uint64_t min;
 	uint64_t max;
 };
diff --git a/reftable/stack.c b/reftable/stack.c
index 1fba96ddb3..77aeac4715 100644
--- a/reftable/stack.c
+++ b/reftable/stack.c
@@ -337,7 +337,6 @@ 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;
 	st->merged = new_merged;
 
 	if (st->tables)
-- 
gitgitgadget