This is an automated email from the ASF dual-hosted git repository.
zeroshade pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/iceberg-go.git
The following commit(s) were added to refs/heads/main by this push:
new 89881cb3e perf(table): avoid string keys for two-file equality deletes
(#2197)
89881cb3e is described below
commit 89881cb3e75d5c14e925c386716dd699754efcf5
Author: Minh Vu <[email protected]>
AuthorDate: Mon Oct 19 18:54:21 2026 +0200
perf(table): avoid string keys for two-file equality deletes (#2197)
* perf(table): avoid string keys for two-file equality delete sets
* test(table): cover equality delete pair cache reuse and allocations
* test(table): benchmark single-file delete reuse
Signed-off-by: Minh Vu <[email protected]>
* perf(table): avoid allocations on cached equality delete lookup
Use Load before allocating the single-flight entry on cache misses,
and fix intrange lint failures in the cache benchmarks.
Signed-off-by: Minh Vu <[email protected]>
---------
Signed-off-by: Minh Vu <[email protected]>
---
table/equality_delete_pair_cache_test.go | 150 +++++++++++++++++++++++++++++++
table/equality_delete_reader.go | 39 +++++++-
2 files changed, 186 insertions(+), 3 deletions(-)
diff --git a/table/equality_delete_pair_cache_test.go
b/table/equality_delete_pair_cache_test.go
new file mode 100644
index 000000000..5211eb1ae
--- /dev/null
+++ b/table/equality_delete_pair_cache_test.go
@@ -0,0 +1,150 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package table
+
+import (
+ "sync"
+ "testing"
+)
+
+func combinationTestFile(id int, key string) *equalityDeleteFileSet {
+ return newEqualityDeleteFileSet(id, &equalityDeleteSet{
+ keys: set[string]{key: {}},
+ fieldIDs: []int{1},
+ colNames: []string{"id"},
+ })
+}
+
+func TestEqualityDeletePairCombinationCache(t *testing.T) {
+ first := combinationTestFile(1, "a")
+ second := combinationTestFile(2, "b")
+ third := combinationTestFile(3, "c")
+
+ t.Run("eager", func(t *testing.T) {
+ multi := make(map[string]*equalityDeleteSet)
+ pairs := make(map[equalityDeleteFilePair]*equalityDeleteSet)
+ get := func(files ...*equalityDeleteFileSet) *equalityDeleteSet
{
+ return equalityDeleteSetForFiles(files, multi, pairs)
+ }
+
+ ab := get(first, second)
+ if get(second, first) != ab || get(first, second, first) != ab {
+ t.Fatal("equivalent pairs must share their merged
delete set")
+ }
+ if len(ab.keys) != 2 {
+ t.Fatalf("pair contains %d keys, want 2", len(ab.keys))
+ }
+ if get(first, third) == ab || get(first, second, third) == ab {
+ t.Fatal("different combinations must not share delete
sets")
+ }
+ if get(third, second, first) != get(first, second, third) {
+ t.Fatal("equivalent three-file groups must share their
merged delete set")
+ }
+ if get(first, first) != first.equalityDeleteSet {
+ t.Fatal("a duplicate-only combination must reuse the
original delete set")
+ }
+ if len(pairs) != 2 || len(multi) != 1 {
+ t.Fatalf("unexpected cache entries: pairs=%d,
multi=%d", len(pairs), len(multi))
+ }
+
+ files := []*equalityDeleteFileSet{first, second}
+ if allocs := testing.AllocsPerRun(100, func() { _ =
equalityDeleteSetForFiles(files, multi, pairs) }); allocs != 0 {
+ t.Fatalf("cached eager pair lookup allocated %g times,
want zero", allocs)
+ }
+ })
+
+ t.Run("lazy", func(t *testing.T) {
+ loader := new(lazyEqualityDeleteLoader)
+ ab := loader.combine([]*equalityDeleteFileSet{first, second})
+ if loader.combine([]*equalityDeleteFileSet{second, first}) !=
ab ||
+ loader.combine([]*equalityDeleteFileSet{first, first,
second}) != ab {
+ t.Fatal("equivalent pairs must reuse the same lazy
delete set")
+ }
+ if loader.combine([]*equalityDeleteFileSet{first, third}) == ab
||
+ loader.combine([]*equalityDeleteFileSet{first, second,
third}) == ab {
+ t.Fatal("different combinations must not share lazy
delete sets")
+ }
+ if loader.combine([]*equalityDeleteFileSet{third, second,
first}) !=
+ loader.combine([]*equalityDeleteFileSet{first, second,
third}) {
+ t.Fatal("equivalent three-file groups must share their
lazy delete set")
+ }
+ })
+}
+
+func TestLazyEqualityDeletePairCombinationConcurrent(t *testing.T) {
+ first := combinationTestFile(1, "a")
+ second := combinationTestFile(2, "b")
+ loader := new(lazyEqualityDeleteLoader)
+ const count = 32
+ var wg sync.WaitGroup
+ results := make([]*equalityDeleteSet, count)
+ for i := range results {
+ wg.Add(1)
+ go func(i int) {
+ defer wg.Done()
+ files := []*equalityDeleteFileSet{first, second}
+ if i%2 == 0 {
+ files[0], files[1] = files[1], files[0]
+ }
+ results[i] = loader.combine(files)
+ }(i)
+ }
+ wg.Wait()
+ for i := 1; i < count; i++ {
+ if results[i] != results[0] {
+ t.Fatalf("worker %d received a different merged delete
set", i)
+ }
+ }
+}
+
+var benchmarkEqualityDeletePairCacheResult *equalityDeleteSet
+
+func BenchmarkEqualityDeleteCombinationCache(b *testing.B) {
+ first := combinationTestFile(1, "a")
+ second := combinationTestFile(2, "b")
+ third := combinationTestFile(3, "c")
+
+ for _, tc := range []struct {
+ name string
+ files []*equalityDeleteFileSet
+ }{
+ {name: "one", files: []*equalityDeleteFileSet{first}},
+ {name: "two", files: []*equalityDeleteFileSet{first, second}},
+ {name: "three", files: []*equalityDeleteFileSet{first, second,
third}},
+ } {
+ b.Run(tc.name+"/eager", func(b *testing.B) {
+ multi := make(map[string]*equalityDeleteSet)
+ pairs :=
make(map[equalityDeleteFilePair]*equalityDeleteSet)
+ benchmarkEqualityDeletePairCacheResult =
equalityDeleteSetForFiles(tc.files, multi, pairs)
+ b.ReportAllocs()
+ b.ResetTimer()
+ for range b.N {
+ benchmarkEqualityDeletePairCacheResult =
equalityDeleteSetForFiles(tc.files, multi, pairs)
+ }
+ })
+ b.Run(tc.name+"/lazy", func(b *testing.B) {
+ loader := new(lazyEqualityDeleteLoader)
+ benchmarkEqualityDeletePairCacheResult =
loader.combine(tc.files)
+ b.ReportAllocs()
+ b.ResetTimer()
+ for range b.N {
+ benchmarkEqualityDeletePairCacheResult =
loader.combine(tc.files)
+ }
+ })
+ }
+}
diff --git a/table/equality_delete_reader.go b/table/equality_delete_reader.go
index e2f75f637..280dcb92f 100644
--- a/table/equality_delete_reader.go
+++ b/table/equality_delete_reader.go
@@ -566,8 +566,18 @@ func (l *lazyEqualityDeleteLoader) combine(files
[]*equalityDeleteFileSet) *equa
return files[0].equalityDeleteSet
}
- key := equalityDeleteSetCombinationKey(files)
- entryValue, _ := l.combinations.LoadOrStore(key,
&lazyEqualityDeleteCombination{})
+ // A comparable pair avoids building a string key for the common
two-file case.
+ // Keep the existing string key for larger combinations.
+ var key any
+ if len(files) == 2 {
+ key = equalityDeletePairKey(files)
+ } else {
+ key = equalityDeleteSetCombinationKey(files)
+ }
+ entryValue, ok := l.combinations.Load(key)
+ if !ok {
+ entryValue, _ = l.combinations.LoadOrStore(key,
&lazyEqualityDeleteCombination{})
+ }
entry := entryValue.(*lazyEqualityDeleteCombination)
entry.once.Do(func() {
entry.set = mergeEqualityDeleteSets(files)
@@ -740,8 +750,9 @@ func buildEqualityDeleteSetsPerTask(
// File IDs are sufficient as the cache key because each ID identifies
one
// immutable delete set with a fixed equality-field group for this call.
sharedSets := make(map[string]*equalityDeleteSet)
+ pairSets := make(map[equalityDeleteFilePair]*equalityDeleteSet)
combine := func(files []*equalityDeleteFileSet) *equalityDeleteSet {
- return equalityDeleteSetForFiles(files, sharedSets)
+ return equalityDeleteSetForFiles(files, sharedSets, pairSets)
}
for i, t := range tasks {
@@ -833,11 +844,22 @@ func buildEqualityDeleteSetsForFiles(
func equalityDeleteSetForFiles(
files []*equalityDeleteFileSet,
sharedSets map[string]*equalityDeleteSet,
+ pairSets map[equalityDeleteFilePair]*equalityDeleteSet,
) *equalityDeleteSet {
files = normalizeEqualityDeleteFiles(files)
if len(files) == 1 {
return files[0].equalityDeleteSet
}
+ if len(files) == 2 {
+ key := equalityDeletePairKey(files)
+ if deleteSet, ok := pairSets[key]; ok {
+ return deleteSet
+ }
+ deleteSet := mergeEqualityDeleteSets(files)
+ pairSets[key] = deleteSet
+
+ return deleteSet
+ }
key := equalityDeleteSetCombinationKey(files)
if deleteSet, ok := sharedSets[key]; ok {
@@ -874,6 +896,17 @@ func normalizeEqualityDeleteFiles(files
[]*equalityDeleteFileSet) []*equalityDel
})
}
+// equalityDeleteFilePair is a comparable cache key for two delete files.
+// normalizeEqualityDeleteFiles ensures the IDs are distinct and sorted.
+type equalityDeleteFilePair struct {
+ firstID int
+ secondID int
+}
+
+func equalityDeletePairKey(files []*equalityDeleteFileSet)
equalityDeleteFilePair {
+ return equalityDeleteFilePair{firstID: files[0].id, secondID:
files[1].id}
+}
+
func equalityDeleteSetCombinationKey(files []*equalityDeleteFileSet) string {
combinationKey := make([]byte, 0, len(files)*8)
for _, file := range files {
