Quadratic tombstone-union work in sorted compaction

perfloop/weaviate · INEFFICIENT ALGORITHM

https://perfloop.ai/t/oss/case_y46xv2nvy0

Verdict

VERIFIED · settled 2026-08-20

What happened: The paired measurements met the required improvement.

Hypothesis

Source inspection of `writeNodeCommits` showed that Phase 2 appends beyond-array `Tombstones` IDs, linearly scans that slice for every beyond-array `TombstonesDeleted` ID, and then insertion-sorts the combined slice. I ran `go test ./adapters/repos/db/vector/hnsw/compact -run '^(TestSortedWriter_TombstoneBeyondNodesArray|TestSortedWriter_RemoveTombstoneBeyondNodesArray|TestSortedWriter_CombinedScenario)$' -count=1`; it passed and confirms round-trip preservation of beyond-array add/remove tombstones and the combined case, but it did not measure timing.

Let A and B be the beyond-array counts in the two maps and K their unique union. The duplicate scans can take O(B(A+B)) comparisons and insertion sort can take O(K²) comparisons and moves; `GraphState` places no cardinality cap on either map. On the compactor path, this runs once per converted file during commit-log maintenance, before output; that path uses a buffered safe-file writer and each tombstone record is nine bytes. Large beyond-array tombstone sets are therefore a plausible CPU cost, but this hunt did not measure their production cardinality or phase share.

Replace the slice membership scan with a set-based union and sort its materialized keys with `sort.Slice`; the removed delta is the repeated linear duplicate search and quadratic insertion shifts. A case should benchmark `SortedWriter.WriteAll` or conversion across a K sweep with add-only, remove-only, overlapping, randomized, and reverse-ordered IDs beyond `Nodes`, and collect a CPU profile showing reduced Phase 2 time. It should also round-trip those cases and verify sorted IDs plus add/remove cancellation semantics.

Change to test: Build the beyond-array tombstone ID union with a set, materialize it once, and use the standard library sorter. Keep writeTombstoneOps as the single cancellation decision so output semantics remain unchanged.

Where it lives

perfloop/weaviate · adapters/repos/db/vector/hnsw/commit_logger.go

Evidence

compactor-beyond-array-tombstone-matrix-1k-10k · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 281739858 71040673 −75.4% (−212311881) −262642961 to −174869572 < −14086993 PASSED

Checks: 2 of 2 passed. Verification: no defect found.

Timeline