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 8ce33af06 perf(table): avoid rebuilding unchanged partition residual
expressions (#2201)
8ce33af06 is described below
commit 8ce33af06edd4538aaa94d5a65fc1b562946a9a9
Author: Minh Vu <[email protected]>
AuthorDate: Mon Oct 19 20:07:42 2026 +0200
perf(table): avoid rebuilding unchanged partition residual expressions
(#2201)
* perf(table): reuse unchanged partition residual expression subtrees
Signed-off-by: Minh Vu <[email protected]>
* test(table): cover unchanged NOT and OR residual allocation paths
Signed-off-by: Minh Vu <[email protected]>
* test(table): benchmark mixed partition residual evaluations
* test(table): verify residual reuse across alternating partitions
* style(table): satisfy nlreturn in residual fast paths
* style(table): separate residual benchmark return
---------
Signed-off-by: Minh Vu <[email protected]>
---
table/partition_residual.go | 18 ++++-
table/partition_residual_bench_test.go | 89 ++++++++++++++++++++++
table/partition_residual_reuse_test.go | 130 +++++++++++++++++++++++++++++++++
3 files changed, 234 insertions(+), 3 deletions(-)
diff --git a/table/partition_residual.go b/table/partition_residual.go
index e47beddeb..690925e01 100644
--- a/table/partition_residual.go
+++ b/table/partition_residual.go
@@ -301,7 +301,11 @@ func (n *partitionResidualNode) residual(
return nil, false, err
}
- return iceberg.NewNot(child), changed, nil
+ if !changed {
+ return n.expr, false, nil
+ }
+
+ return iceberg.NewNot(child), true, nil
case partitionResidualAnd:
left, leftChanged, err := n.left.residual(partition)
if err != nil {
@@ -316,7 +320,11 @@ func (n *partitionResidualNode) residual(
return nil, false, err
}
- return iceberg.NewAnd(left, right), leftChanged ||
rightChanged, nil
+ if !leftChanged && !rightChanged {
+ return n.expr, false, nil
+ }
+
+ return iceberg.NewAnd(left, right), true, nil
case partitionResidualOr:
left, leftChanged, err := n.left.residual(partition)
if err != nil {
@@ -331,7 +339,11 @@ func (n *partitionResidualNode) residual(
return nil, false, err
}
- return iceberg.NewOr(left, right), leftChanged || rightChanged,
nil
+ if !leftChanged && !rightChanged {
+ return n.expr, false, nil
+ }
+
+ return iceberg.NewOr(left, right), true, nil
}
return n.expr, false, nil
diff --git a/table/partition_residual_bench_test.go
b/table/partition_residual_bench_test.go
index f7ae51bad..c082e1173 100644
--- a/table/partition_residual_bench_test.go
+++ b/table/partition_residual_bench_test.go
@@ -18,6 +18,7 @@
package table
import (
+ "fmt"
"testing"
"github.com/apache/iceberg-go"
@@ -104,3 +105,91 @@ func BenchmarkPartitionResidualPlanning(b *testing.B) {
})
}
}
+
+// BenchmarkPartitionResidualUnchangedSubtrees measures per-file residual
+// evaluation when either no predicate simplifies or just one predicate does.
+// The balanced tree keeps the unaffected branches representative of filters
+// containing many conditions.
+func BenchmarkPartitionResidualUnchangedSubtrees(b *testing.B) {
+ schema := partitionResidualTestSchema()
+ spec := iceberg.NewPartitionSpec(iceberg.PartitionField{
+ SourceIDs: []int{1}, FieldID: 1000, Name: "tenant_id",
Transform: iceberg.IdentityTransform{},
+ })
+
+ for _, predicateCount := range []int{8, 32} {
+ predicates := make([]iceberg.BooleanExpression, 0,
predicateCount)
+ predicates = append(predicates,
iceberg.EqualTo(iceberg.Reference("tenant_id"), "acme"))
+ for i := 1; i < predicateCount; i++ {
+ predicates = append(predicates,
iceberg.GreaterThan(iceberg.Reference("amount"), int64(i)))
+ }
+
+ bound, err := iceberg.BindExpr(schema,
benchmarkBalancedPartitionResidualAnd(predicates), true)
+ if err != nil {
+ b.Fatal(err)
+ }
+ evaluator, err := newPartitionResidualEvaluator(schema, &spec,
bound, true)
+ if err != nil {
+ b.Fatal(err)
+ }
+ if evaluator == nil {
+ b.Fatal("expected partition residual evaluator")
+ }
+
+ for _, tc := range []struct {
+ name string
+ value any
+ present bool
+ mixed bool
+ }{
+ {name: "missing"},
+ {name: "null", present: true},
+ {name: "one-simplified", value: "acme", present: true},
+ {name: "mixed", mixed: true},
+ } {
+ b.Run(fmt.Sprintf("predicates=%d/%s/files=4096",
predicateCount, tc.name), func(b *testing.B) {
+ partitions := make([]map[int]any, 4096)
+ for i := range partitions {
+ partitions[i] = make(map[int]any, 1)
+ if tc.mixed {
+ switch i % 4 {
+ case 1:
+ partitions[i][1000] =
nil
+ case 2:
+ partitions[i][1000] =
"acme"
+ case 3:
+ partitions[i][1000] =
"other"
+ }
+ } else if tc.present {
+ partitions[i][1000] = tc.value
+ }
+ }
+
+ b.ReportAllocs()
+ b.ResetTimer()
+ for b.Loop() {
+ for _, partition := range partitions {
+ residual, _, err :=
evaluator.residual(partition)
+ if err != nil {
+ b.Fatal(err)
+ }
+ partitionResidualBenchmarkSink
= residual
+ }
+ }
+ b.StopTimer()
+ b.ReportMetric(float64(len(partitions)),
"files/op")
+ })
+ }
+ }
+}
+
+func benchmarkBalancedPartitionResidualAnd(predicates
[]iceberg.BooleanExpression) iceberg.BooleanExpression {
+ if len(predicates) == 1 {
+ return predicates[0]
+ }
+ mid := len(predicates) / 2
+
+ return iceberg.NewAnd(
+ benchmarkBalancedPartitionResidualAnd(predicates[:mid]),
+ benchmarkBalancedPartitionResidualAnd(predicates[mid:]),
+ )
+}
diff --git a/table/partition_residual_reuse_test.go
b/table/partition_residual_reuse_test.go
new file mode 100644
index 000000000..914eac4ea
--- /dev/null
+++ b/table/partition_residual_reuse_test.go
@@ -0,0 +1,130 @@
+// 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 (
+ "testing"
+
+ "github.com/apache/iceberg-go"
+ "github.com/stretchr/testify/require"
+)
+
+func TestPartitionResidualEvaluatorReusesUnchangedSubtrees(t *testing.T) {
+ schema := partitionResidualTestSchema()
+ spec := iceberg.NewPartitionSpec(iceberg.PartitionField{
+ SourceIDs: []int{1}, FieldID: 1000, Name: "tenant_id",
Transform: iceberg.IdentityTransform{},
+ })
+
+ tenant := iceberg.EqualTo(iceberg.Reference("tenant_id"), "acme")
+ amount := iceberg.Reference("amount")
+ opaque := iceberg.NewAnd(
+ iceberg.NewNot(iceberg.GreaterThan(amount, int64(100))),
+ iceberg.NewOr(
+ iceberg.LessThan(amount, int64(20)),
+ iceberg.GreaterThan(amount, int64(200)),
+ ),
+ )
+
+ tests := []struct {
+ name string
+ filter iceberg.BooleanExpression
+ partitionValue string
+ want iceberg.BooleanExpression
+ }{
+ {name: "and", filter: iceberg.NewAnd(tenant, opaque),
partitionValue: "acme", want: opaque},
+ {name: "and-right", filter: iceberg.NewAnd(opaque, tenant),
partitionValue: "acme", want: opaque},
+ {name: "or", filter: iceberg.NewOr(tenant, opaque),
partitionValue: "other", want: opaque},
+ {name: "or-right", filter: iceberg.NewOr(opaque, tenant),
partitionValue: "other", want: opaque},
+ {name: "not", filter: iceberg.NewNot(iceberg.NewOr(tenant,
opaque)), partitionValue: "other", want: iceberg.NewNot(opaque)},
+ {name: "not-right", filter:
iceberg.NewNot(iceberg.NewOr(opaque, tenant)), partitionValue: "other", want:
iceberg.NewNot(opaque)},
+ }
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ evaluator := boundPartitionResidualEvaluator(t, schema,
spec, tt.filter)
+ want, err := iceberg.BindExpr(schema, tt.want, true)
+ require.NoError(t, err)
+
+ got, changed, err :=
evaluator.residual(map[int]any{1000: tt.partitionValue})
+ require.NoError(t, err)
+ require.True(t, changed)
+ require.NotNil(t, got)
+ require.True(t, got.Equals(want), "expected %s, got
%s", want, got)
+
+ for _, partition := range []map[int]any{{}, {1000:
nil}} {
+ got, changed, err =
evaluator.residual(partition)
+ require.NoError(t, err)
+ require.False(t, changed)
+ require.Nil(t, got)
+ }
+ got, changed, err =
evaluator.residual(map[int]any{1000: tt.partitionValue})
+ require.NoError(t, err)
+ require.True(t, changed)
+ require.True(t, got.Equals(want), "interleaved
unchanged files must not affect later residuals")
+ })
+ }
+}
+
+func TestPartitionResidualEvaluatorUnchangedSubtreeAllocations(t *testing.T) {
+ schema := partitionResidualTestSchema()
+ spec := iceberg.NewPartitionSpec(iceberg.PartitionField{
+ SourceIDs: []int{1}, FieldID: 1000, Name: "tenant_id",
Transform: iceberg.IdentityTransform{},
+ })
+ tenant := iceberg.EqualTo(iceberg.Reference("tenant_id"), "acme")
+ opaque := iceberg.NewOr(
+ iceberg.GreaterThan(iceberg.Reference("amount"), int64(100)),
+ iceberg.NewNot(iceberg.LessThan(iceberg.Reference("amount"),
int64(20))),
+ )
+
+ for _, tt := range []struct {
+ name string
+ filter iceberg.BooleanExpression
+ }{
+ {name: "and", filter: iceberg.NewAnd(tenant, opaque)},
+ {name: "or", filter: iceberg.NewOr(tenant, opaque)},
+ {name: "not", filter: iceberg.NewNot(iceberg.NewOr(tenant,
opaque))},
+ } {
+ t.Run(tt.name, func(t *testing.T) {
+ evaluator := boundPartitionResidualEvaluator(t, schema,
spec, tt.filter)
+ for _, tc := range []struct {
+ name string
+ partition map[int]any
+ }{
+ {name: "missing", partition: map[int]any{}},
+ {name: "null", partition: map[int]any{1000:
nil}},
+ } {
+ t.Run(tc.name, func(t *testing.T) {
+ // The node must retain the expression
it built at
+ // evaluator creation instead of
allocating a new tree.
+ nodeExpr, changed, err :=
evaluator.root.residual(
+
borrowedPartitionRecord{partition: tc.partition, partitionType:
evaluator.partitionType})
+ require.NoError(t, err)
+ require.False(t, changed)
+ require.True(t,
nodeExpr.Equals(evaluator.root.expr))
+
+ allocs := testing.AllocsPerRun(100,
func() {
+ residual, changed, err :=
evaluator.residual(tc.partition)
+ if err != nil || changed ||
residual != nil {
+ panic("unchanged
partition residual must be nil without an error")
+ }
+ })
+ require.Zero(t, allocs)
+ })
+ }
+ })
+ }
+}
