You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@iceberg.apache.org by ze...@apache.org on 2026/10/20 17:15:02 UTC
(iceberg-go) branch main updated: perf(table): inline snapshot ancestry visit tracking (#2223)
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 305d6adff perf(table): inline snapshot ancestry visit tracking (#2223)
305d6adff is described below
commit 305d6adfff7cf8322ac04f31a64554f1a7561fb0
Author: Minh Vu <vu...@gmail.com>
AuthorDate: Tue Oct 20 19:14:56 2026 +0200
perf(table): inline snapshot ancestry visit tracking (#2223)
* perf(table): inline snapshot ancestry visit tracking
Signed-off-by: Minh Vu <vu...@gmail.com>
* fix(table): address snapshot ancestry lint findings
Signed-off-by: Minh Vu <vu...@gmail.com>
---------
Signed-off-by: Minh Vu <vu...@gmail.com>
---
table/snapshot_ancestry.go | 66 ++++++++++++++++-----
table/snapshot_ancestry_bench_test.go | 87 ++++++++++++++++++++++++++++
table/snapshot_ancestry_inline_test.go | 102 +++++++++++++++++++++++++++++++++
3 files changed, 241 insertions(+), 14 deletions(-)
diff --git a/table/snapshot_ancestry.go b/table/snapshot_ancestry.go
index ede556322..7fe95c653 100644
--- a/table/snapshot_ancestry.go
+++ b/table/snapshot_ancestry.go
@@ -17,10 +17,53 @@
package table
+import "slices"
+
// SnapshotLookup returns the snapshot for the given id, or nil if not found.
// It matches the signature of Metadata.SnapshotByID.
type SnapshotLookup func(id int64) *Snapshot
+// Most ancestry queries traverse only a few snapshots. Keep those IDs inline
+// instead of hashing every hop. Longer or malformed chains still use a map
+// so cycle detection stays linear and cannot loop forever.
+const inlineSnapshotVisitLimit = 16
+
+type snapshotVisitSet struct {
+ inline [inlineSnapshotVisitLimit]int64
+ count int
+ overflow map[int64]struct{}
+}
+
+// seenOrAdd reports whether id was already visited.
+func (s *snapshotVisitSet) seenOrAdd(id int64) bool {
+ if s.overflow != nil {
+ if _, seen := s.overflow[id]; seen {
+ return true
+ }
+ s.overflow[id] = struct{}{}
+
+ return false
+ }
+
+ if slices.Contains(s.inline[:s.count], id) {
+ return true
+ }
+ if s.count < len(s.inline) {
+ s.inline[s.count] = id
+ s.count++
+
+ return false
+ }
+
+ s.overflow = make(map[int64]struct{}, 2*len(s.inline))
+ for _, previous := range s.inline {
+ s.overflow[previous] = struct{}{}
+ }
+ s.overflow[id] = struct{}{}
+
+ return false
+}
+
// AncestorsOf walks the parent chain starting from snapshotID and yields
// every snapshot reachable via ParentSnapshotID, including the starting
// snapshot itself. Iteration stops when a snapshot has no parent, the
@@ -57,14 +100,13 @@ func AncestorsOf(snapshotID int64, lookup SnapshotLookup) []Snapshot {
// Returns an empty slice and false when snapshotID cannot be resolved.
func AncestorsOfChecked(snapshotID int64, lookup SnapshotLookup) ([]Snapshot, bool) {
var ancestors []Snapshot
- visited := make(map[int64]struct{})
+ var visited snapshotVisitSet
id := snapshotID
for {
- if _, seen := visited[id]; seen {
+ if visited.seenOrAdd(id) {
return ancestors, false
}
- visited[id] = struct{}{}
snap := lookup(id)
if snap == nil {
@@ -106,18 +148,17 @@ func AncestorsBetween(latestID, baseID int64, lookup SnapshotLookup) ([]Snapshot
}
var between []Snapshot
- visited := make(map[int64]struct{})
+ var visited snapshotVisitSet
id := latestID
for {
if id == baseID {
return between, true
}
- if _, seen := visited[id]; seen {
+ if visited.seenOrAdd(id) {
// Cycle detected before reaching baseID.
break
}
- visited[id] = struct{}{}
snap := lookup(id)
if snap == nil {
@@ -148,11 +189,11 @@ func AncestorsBetween(latestID, baseID int64, lookup SnapshotLookup) ([]Snapshot
// semantics are stricter (conservative) — broken chains return false
// rather than matching an unreachable ancestor id.
func IsAncestorOf(snapshotID, ancestorID int64, lookup SnapshotLookup) bool {
- visited := make(map[int64]struct{})
+ var visited snapshotVisitSet
id := snapshotID
for {
- if _, seen := visited[id]; seen {
+ if visited.seenOrAdd(id) {
return false
}
@@ -161,16 +202,13 @@ func IsAncestorOf(snapshotID, ancestorID int64, lookup SnapshotLookup) bool {
return false
}
- // Equality check must come BEFORE the visited write so that an
- // ancestor reached in the second hop of a cycle (e.g. 1 ↔ 2,
- // IsAncestorOf(1, 2)) is correctly returned as true before
- // cycle detection fires on the next iteration.
+ // Resolve before matching, so an absent ancestor ID does not
+ // count as reachable. An ID inside a cycle succeeds on its first
+ // visit, before cycle detection can reject a repeated ID.
if id == ancestorID {
return true
}
- visited[id] = struct{}{}
-
if snap.ParentSnapshotID == nil {
return false
}
diff --git a/table/snapshot_ancestry_bench_test.go b/table/snapshot_ancestry_bench_test.go
new file mode 100644
index 000000000..79517fdd6
--- /dev/null
+++ b/table/snapshot_ancestry_bench_test.go
@@ -0,0 +1,87 @@
+// 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 (
+ "fmt"
+ "testing"
+)
+
+var (
+ benchmarkSnapshotAncestrySnapshots []Snapshot
+ benchmarkSnapshotAncestryFound bool
+)
+
+// End-to-end ancestry traversals, including snapshot lookups and result slices.
+// Chain setup is outside the timed region. The depth=17 case exercises the
+// transition from inline IDs to the map fallback.
+func BenchmarkSnapshotAncestry(b *testing.B) {
+ for _, depth := range []int64{1, 4, 8, 9, 16, 17, 32, 64, 256} {
+ lookup := buildChain(depth)
+
+ b.Run(fmt.Sprintf("is_ancestor/reachable/depth=%d", depth), func(b *testing.B) {
+ b.ReportAllocs()
+ for b.Loop() {
+ benchmarkSnapshotAncestryFound = IsAncestorOf(depth, 1, lookup)
+ }
+ if !benchmarkSnapshotAncestryFound {
+ b.Fatal("expected root to be reachable")
+ }
+ })
+
+ b.Run(fmt.Sprintf("is_ancestor/missing/depth=%d", depth), func(b *testing.B) {
+ b.ReportAllocs()
+ for b.Loop() {
+ benchmarkSnapshotAncestryFound = IsAncestorOf(depth, -1, lookup)
+ }
+ if benchmarkSnapshotAncestryFound {
+ b.Fatal("missing ancestor was marked reachable")
+ }
+ })
+
+ b.Run(fmt.Sprintf("ancestors_between/reachable/depth=%d", depth), func(b *testing.B) {
+ b.ReportAllocs()
+ for b.Loop() {
+ benchmarkSnapshotAncestrySnapshots, benchmarkSnapshotAncestryFound = AncestorsBetween(depth, 1, lookup)
+ }
+ if !benchmarkSnapshotAncestryFound || int64(len(benchmarkSnapshotAncestrySnapshots)) != depth-1 {
+ b.Fatal("incorrect ancestry between snapshots")
+ }
+ })
+
+ b.Run(fmt.Sprintf("ancestors_between/missing/depth=%d", depth), func(b *testing.B) {
+ b.ReportAllocs()
+ for b.Loop() {
+ benchmarkSnapshotAncestrySnapshots, benchmarkSnapshotAncestryFound = AncestorsBetween(depth, -1, lookup)
+ }
+ if benchmarkSnapshotAncestryFound || int64(len(benchmarkSnapshotAncestrySnapshots)) != depth {
+ b.Fatal("unexpected complete ancestry for missing base")
+ }
+ })
+
+ b.Run(fmt.Sprintf("ancestors_of/depth=%d", depth), func(b *testing.B) {
+ b.ReportAllocs()
+ for b.Loop() {
+ benchmarkSnapshotAncestrySnapshots, benchmarkSnapshotAncestryFound = AncestorsOfChecked(depth, lookup)
+ }
+ if !benchmarkSnapshotAncestryFound || int64(len(benchmarkSnapshotAncestrySnapshots)) != depth {
+ b.Fatal("incorrect complete ancestry")
+ }
+ })
+ }
+}
diff --git a/table/snapshot_ancestry_inline_test.go b/table/snapshot_ancestry_inline_test.go
new file mode 100644
index 000000000..66a489613
--- /dev/null
+++ b/table/snapshot_ancestry_inline_test.go
@@ -0,0 +1,102 @@
+// 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 (
+ "fmt"
+ "testing"
+)
+
+// Malformed cycles must be detected on both sides of the inline-to-map
+// transition, without incorrectly rejecting ancestors inside the cycle.
+func TestSnapshotAncestryCycleAcrossInlineBoundary(t *testing.T) {
+ for _, count := range []int{2, 8, 9, 16, 17, 32, 128} {
+ t.Run(fmt.Sprintf("snapshots=%d", count), func(t *testing.T) {
+ lookup := buildLongSnapshotCycle(count)
+
+ ancestors, complete := AncestorsOfChecked(1, lookup)
+ if complete || len(ancestors) != count {
+ t.Fatalf("AncestorsOfChecked: complete=%t, count=%d; want false, %d",
+ complete, len(ancestors), count)
+ }
+ for i, snap := range ancestors {
+ if snap.SnapshotID != int64(i+1) {
+ t.Fatalf("ancestor[%d]=%d, want %d", i, snap.SnapshotID, i+1)
+ }
+ }
+
+ between, baseFound := AncestorsBetween(1, -1, lookup)
+ if baseFound || len(between) != count {
+ t.Fatalf("AncestorsBetween: baseFound=%t, count=%d; want false, %d",
+ baseFound, len(between), count)
+ }
+ if IsAncestorOf(1, -1, lookup) {
+ t.Fatal("missing ancestor must not be reachable through a cycle")
+ }
+ if !IsAncestorOf(1, int64(count), lookup) {
+ t.Fatal("reachable ancestor inside a cycle was rejected")
+ }
+ })
+ }
+}
+
+func TestSnapshotAncestryMissingParentAcrossInlineBoundary(t *testing.T) {
+ for _, count := range []int64{8, 9, 16, 17, 32, 128} {
+ t.Run(fmt.Sprintf("snapshots=%d", count), func(t *testing.T) {
+ chain := buildChain(count)
+ lookup := func(id int64) *Snapshot {
+ if id == 1 {
+ return nil
+ }
+
+ return chain(id)
+ }
+
+ ancestors, complete := AncestorsOfChecked(count, lookup)
+ if complete || int64(len(ancestors)) != count-1 {
+ t.Fatalf("AncestorsOfChecked: complete=%t, count=%d; want false, %d",
+ complete, len(ancestors), count-1)
+ }
+
+ between, found := AncestorsBetween(count, -1, lookup)
+ if found || int64(len(between)) != count-1 {
+ t.Fatalf("AncestorsBetween: found=%t, count=%d; want false, %d",
+ found, len(between), count-1)
+ }
+ if IsAncestorOf(count, 1, lookup) {
+ t.Fatal("an unresolved ancestor must not match")
+ }
+ })
+ }
+}
+
+func buildLongSnapshotCycle(count int) SnapshotLookup {
+ snapshots := make(map[int64]*Snapshot, count)
+ for i := 1; i <= count; i++ {
+ parent := int64(i + 1)
+ if i == count {
+ parent = 1
+ }
+ snapshots[int64(i)] = &Snapshot{
+ SnapshotID: int64(i),
+ ParentSnapshotID: &parent,
+ }
+ }
+
+ return func(id int64) *Snapshot { return snapshots[id] }
+}