You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@iceberg.apache.org by "joyhaldar (via GitHub)" <gi...@apache.org> on 2026/01/12 13:57:36 UTC
[PR] Core: Optimize ExpireSnapshots by eliminating redundant ancestor traversal [iceberg]
joyhaldar opened a new pull request, #15038:
URL: https://github.com/apache/iceberg/pull/15038
### Description
Currently when expiring snapshots, the code walks the ancestor chain twice:
1. [computeBranchSnapshotsToRetain](https://github.com/apache/iceberg/blob/7f81e1e93084e50fa3676c2e131722f66a26b385/core/src/main/java/org/apache/iceberg/RemoveSnapshots.java#L316) - finds snapshots to retain
2. [unreferencedSnapshotsToRetain](https://github.com/apache/iceberg/blob/7f81e1e93084e50fa3676c2e131722f66a26b385/core/src/main/java/org/apache/iceberg/RemoveSnapshots.java#L331) - finds all referenced snapshots for orphan detection
This PR combines both into a single walk, tracking retained and referenced snapshots together. also skips the orphan check entirely when all snapshots are referenced, common case for tables without orphans.
### Complexity
| Scenario | Before | After |
|----------|--------|-------|
| Tables without orphans | O(2N + k) | O(N) |
| Tables with orphans | O(2N + k) | O(2N) |
Where N = total snapshots, k = retained snapshots.
### Testing
- All existing `TestRemoveSnapshots` tests pass.
- Added `testExpireSnapshotsWithoutOrphans` and `testExpireSnapshotsWithOrphans` to validate both paths.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Optimize ExpireSnapshots by combining ancestor traversals [iceberg]
Posted by "joyhaldar (via GitHub)" <gi...@apache.org>.
joyhaldar commented on PR #15038:
URL: https://github.com/apache/iceberg/pull/15038#issuecomment-3739507886
> How many snapshots you have typically?
>
> I feel that the code complexity is increasing quite a bit, and I expect that we should not have high enough number of snapshots to make this worth
That's a fair point. Most tables have a few thousand snapshots where this won't make a noticeable difference.
I was exploring the snapshot expiration code to understand the flow and noticed the duplicate traversal. The change made sense to me at the time, but I understand if the added complexity isn't worth it.
Happy to close this if you feel the same way.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Optimize ExpireSnapshots by combining ancestor traversals [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #15038:
URL: https://github.com/apache/iceberg/pull/15038#discussion_r2683026661
##########
core/src/main/java/org/apache/iceberg/RemoveSnapshots.java:
##########
@@ -296,53 +301,51 @@ private Map<String, SnapshotRef> computeRetainedRefs(Map<String, SnapshotRef> re
return retainedRefs;
}
- private Set<Long> computeAllBranchSnapshotsToRetain(Collection<SnapshotRef> refs) {
- Set<Long> branchSnapshotsToRetain = Sets.newHashSet();
+ private void computeAllBranchSnapshotsToRetain(
+ Collection<SnapshotRef> refs, Set<Long> idsToRetain, Set<Long> referencedSnapshotIds) {
for (SnapshotRef ref : refs) {
if (ref.isBranch()) {
long expireSnapshotsOlderThan =
ref.maxSnapshotAgeMs() != null ? now - ref.maxSnapshotAgeMs() : defaultExpireOlderThan;
int minSnapshotsToKeep =
ref.minSnapshotsToKeep() != null ? ref.minSnapshotsToKeep() : defaultMinNumSnapshots;
- branchSnapshotsToRetain.addAll(
- computeBranchSnapshotsToRetain(
- ref.snapshotId(), expireSnapshotsOlderThan, minSnapshotsToKeep));
- }
- }
-
- return branchSnapshotsToRetain;
- }
-
- private Set<Long> computeBranchSnapshotsToRetain(
- long snapshot, long expireSnapshotsOlderThan, int minSnapshotsToKeep) {
- Set<Long> idsToRetain = Sets.newHashSet();
- for (Snapshot ancestor : SnapshotUtil.ancestorsOf(snapshot, base::snapshot)) {
- if (idsToRetain.size() < minSnapshotsToKeep
- || ancestor.timestampMillis() >= expireSnapshotsOlderThan) {
- idsToRetain.add(ancestor.snapshotId());
+ computeBranchSnapshotsToRetain(
+ ref.snapshotId(),
+ expireSnapshotsOlderThan,
+ minSnapshotsToKeep,
+ idsToRetain,
+ referencedSnapshotIds);
} else {
- return idsToRetain;
+ referencedSnapshotIds.add(ref.snapshotId());
}
}
-
- return idsToRetain;
}
- private Set<Long> unreferencedSnapshotsToRetain(Collection<SnapshotRef> refs) {
- Set<Long> referencedSnapshots = Sets.newHashSet();
- for (SnapshotRef ref : refs) {
- if (ref.isBranch()) {
- for (Snapshot snapshot : SnapshotUtil.ancestorsOf(ref.snapshotId(), base::snapshot)) {
- referencedSnapshots.add(snapshot.snapshotId());
+ private void computeBranchSnapshotsToRetain(
+ long snapshot,
+ long expireSnapshotsOlderThan,
+ int minSnapshotsToKeep,
+ Set<Long> idsToRetain,
+ Set<Long> referencedSnapshotIds) {
+ boolean stillRetaining = true;
+
+ for (Snapshot ancestor : SnapshotUtil.ancestorsOf(snapshot, base::snapshot)) {
+ referencedSnapshotIds.add(ancestor.snapshotId());
+ if (stillRetaining) {
+ if (idsToRetain.size() < minSnapshotsToKeep
+ || ancestor.timestampMillis() >= expireSnapshotsOlderThan) {
+ idsToRetain.add(ancestor.snapshotId());
+ } else {
+ stillRetaining = false;
Review Comment:
Why do we don't return here as it was before?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Optimize ExpireSnapshots by combining ancestor traversals [iceberg]
Posted by "joyhaldar (via GitHub)" <gi...@apache.org>.
joyhaldar commented on PR #15038:
URL: https://github.com/apache/iceberg/pull/15038#issuecomment-3741615520
@amogh-jahagirdar , @pvary, I agree with your points, I will consider reopening this PR if I have concrete benchmark numbers to share, but will close it for the time being.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Optimize ExpireSnapshots by combining ancestor traversals [iceberg]
Posted by "joyhaldar (via GitHub)" <gi...@apache.org>.
joyhaldar closed pull request #15038: Core: Optimize ExpireSnapshots by combining ancestor traversals
URL: https://github.com/apache/iceberg/pull/15038
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Optimize ExpireSnapshots by combining ancestor traversals [iceberg]
Posted by "joyhaldar (via GitHub)" <gi...@apache.org>.
joyhaldar commented on code in PR #15038:
URL: https://github.com/apache/iceberg/pull/15038#discussion_r2683081745
##########
core/src/main/java/org/apache/iceberg/RemoveSnapshots.java:
##########
@@ -296,53 +301,51 @@ private Map<String, SnapshotRef> computeRetainedRefs(Map<String, SnapshotRef> re
return retainedRefs;
}
- private Set<Long> computeAllBranchSnapshotsToRetain(Collection<SnapshotRef> refs) {
- Set<Long> branchSnapshotsToRetain = Sets.newHashSet();
+ private void computeAllBranchSnapshotsToRetain(
+ Collection<SnapshotRef> refs, Set<Long> idsToRetain, Set<Long> referencedSnapshotIds) {
for (SnapshotRef ref : refs) {
if (ref.isBranch()) {
long expireSnapshotsOlderThan =
ref.maxSnapshotAgeMs() != null ? now - ref.maxSnapshotAgeMs() : defaultExpireOlderThan;
int minSnapshotsToKeep =
ref.minSnapshotsToKeep() != null ? ref.minSnapshotsToKeep() : defaultMinNumSnapshots;
- branchSnapshotsToRetain.addAll(
- computeBranchSnapshotsToRetain(
- ref.snapshotId(), expireSnapshotsOlderThan, minSnapshotsToKeep));
- }
- }
-
- return branchSnapshotsToRetain;
- }
-
- private Set<Long> computeBranchSnapshotsToRetain(
- long snapshot, long expireSnapshotsOlderThan, int minSnapshotsToKeep) {
- Set<Long> idsToRetain = Sets.newHashSet();
- for (Snapshot ancestor : SnapshotUtil.ancestorsOf(snapshot, base::snapshot)) {
- if (idsToRetain.size() < minSnapshotsToKeep
- || ancestor.timestampMillis() >= expireSnapshotsOlderThan) {
- idsToRetain.add(ancestor.snapshotId());
+ computeBranchSnapshotsToRetain(
+ ref.snapshotId(),
+ expireSnapshotsOlderThan,
+ minSnapshotsToKeep,
+ idsToRetain,
+ referencedSnapshotIds);
} else {
- return idsToRetain;
+ referencedSnapshotIds.add(ref.snapshotId());
}
}
-
- return idsToRetain;
}
- private Set<Long> unreferencedSnapshotsToRetain(Collection<SnapshotRef> refs) {
- Set<Long> referencedSnapshots = Sets.newHashSet();
- for (SnapshotRef ref : refs) {
- if (ref.isBranch()) {
- for (Snapshot snapshot : SnapshotUtil.ancestorsOf(ref.snapshotId(), base::snapshot)) {
- referencedSnapshots.add(snapshot.snapshotId());
+ private void computeBranchSnapshotsToRetain(
+ long snapshot,
+ long expireSnapshotsOlderThan,
+ int minSnapshotsToKeep,
+ Set<Long> idsToRetain,
+ Set<Long> referencedSnapshotIds) {
+ boolean stillRetaining = true;
+
+ for (Snapshot ancestor : SnapshotUtil.ancestorsOf(snapshot, base::snapshot)) {
+ referencedSnapshotIds.add(ancestor.snapshotId());
+ if (stillRetaining) {
+ if (idsToRetain.size() < minSnapshotsToKeep
+ || ancestor.timestampMillis() >= expireSnapshotsOlderThan) {
+ idsToRetain.add(ancestor.snapshotId());
+ } else {
+ stillRetaining = false;
Review Comment:
Thank you for your review.
The original code returned early here, but `unreferencedSnapshotsToRetain` would walk the full chain again anyway. So the early exit wasn't saving any work.
Now we walk once and collect both retained and referenced snapshots together.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Optimize ExpireSnapshots by combining ancestor traversals [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on PR #15038:
URL: https://github.com/apache/iceberg/pull/15038#issuecomment-3739481788
How many snapshots you have typically?
I feel that the code complexity is increasing quite a bit, and I expect that we should not have high enough number of snapshots to make this worth
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org