You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@iceberg.apache.org by "fallintoplace (via GitHub)" <gi...@apache.org> on 2026/10/03 17:15:51 UTC
[PR] perf(table): fast-path IN metrics pruning with extrema [iceberg-go]
fallintoplace opened a new pull request, #2117:
URL: https://github.com/apache/iceberg-go/pull/2117
## What
Skip an `IN` predicate when file bounds cannot match any value in the set.
## Why
Manifest evaluation repeats member scans and allocations for every file.
## Implementation
Compare file bounds with cached set extrema first. Keep exact member filtering when bounds overlap, including sparse sets.
Benchmarks compare base `fa5309b` with this change (`078dce9`). Each operation evaluates 10,000 files; values are medians from 7 runs of 1 second on Go 1.26.3, darwin/arm64 (Apple M1 Pro).
| IN values | File bounds | Time, base → head | B/op, base → head | Allocs/op, base → head |
| ---: | --- | ---: | ---: | ---: |
| 10 | Below set | 7.25 → 1.84 ms | 2,320,008 → 720,002 | 40,000 → 30,000 |
| 10 | Above set | 5.89 → 1.34 ms | 2,240,006 → 640,001 | 20,000 → 10,000 |
| 50 | Below set | 24.38 → 1.91 ms | 9,680,027 → 720,002 | 40,000 → 30,000 |
| 50 | Above set | 19.62 → 1.38 ms | 9,600,018 → 640,001 | 20,000 → 10,000 |
| 200 | Below set | 88.60 → 1.85 ms | 35,280,113 → 720,002 | 40,000 → 30,000 |
| 200 | Above set | 73.06 → 1.50 ms | 35,240,105 → 680,002 | 30,000 → 20,000 |
Overlap and sparse-gap controls retain exact member filtering and unchanged allocation counts.
Command:
```sh
go test ./table -run '^$' -bench '^BenchmarkInclusiveMetricsEvalInPredicate/int32/in=(10|50|200)/(below-set|above-set)$' -benchmem -benchtime=1s -count=7 -cpu=1
```
--
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] perf(table): fast-path IN metrics pruning with extrema [iceberg-go]
Posted by "zeroshade (via GitHub)" <gi...@apache.org>.
zeroshade merged PR #2117:
URL: https://github.com/apache/iceberg-go/pull/2117
--
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] perf(table): fast-path IN metrics pruning with extrema [iceberg-go]
Posted by "laskoviymishka (via GitHub)" <gi...@apache.org>.
laskoviymishka commented on code in PR #2117:
URL: https://github.com/apache/iceberg-go/pull/2117#discussion_r4224600034
##########
table/evaluators.go:
##########
@@ -326,6 +330,52 @@ func getCmpLiteral(boundary iceberg.Literal) func(iceberg.Literal, iceberg.Liter
panic(iceberg.ErrType)
}
+// compareLiteralValues requires the same concrete literal type on both sides,
+// as guaranteed for bound predicates. A mismatched type assertion will panic.
+func compareLiteralValues[T iceberg.LiteralType](left, right iceberg.Literal) int {
+ leftValue := left.(iceberg.TypedLiteral[T])
+ rightValue := right.(iceberg.TypedLiteral[T])
+
+ return leftValue.Comparator()(leftValue.Value(), rightValue.Value())
+}
+
+// Keep this dispatch aligned with getCmpLiteral, removeBoundCheck, and
+// allBoundCheck when adding a new literal type.
+func compareBoundLiterals(left, right iceberg.Literal) int {
Review Comment:
The "keep aligned" comment lands, but a new literal type added to one switch and not this one still only shows up as a runtime panic. A small table test that runs each primitive type through both `compareBoundLiterals` and `getCmpLiteral` and asserts they agree would pin the drift mechanically. If you'd rather, reimplementing `getCmpLiteral` as a thin wrapper over `compareBoundLiterals` drops one of the four switches outright and removes the per-file closure alloc that zeroshade's thread is about.
##########
table/evaluators.go:
##########
@@ -1142,34 +1192,81 @@ func (m *inclusiveMetricsEval) VisitNotEqual(iceberg.BoundTerm, iceberg.Literal)
}
func (m *inclusiveMetricsEval) VisitIn(t iceberg.BoundTerm, s iceberg.Set[iceberg.Literal]) bool {
+ return m.visitIn(t, s, nil, nil)
+}
+
+// VisitInWithExtrema expects minLit and maxLit to either both be the actual
+// extrema of s or both be nil. A partial pair is treated as unavailable and
+// follows the same path as VisitIn.
+func (m *inclusiveMetricsEval) VisitInWithExtrema(
+ t iceberg.BoundTerm, s iceberg.Set[iceberg.Literal], minLit, maxLit iceberg.Literal,
+) bool {
+ return m.visitIn(t, s, minLit, maxLit)
+}
+
+func (m *inclusiveMetricsEval) visitIn(
+ t iceberg.BoundTerm, s iceberg.Set[iceberg.Literal], minLit, maxLit iceberg.Literal,
+) bool {
fieldID := t.Ref().Field().ID
if m.containsNullsOnly(fieldID) || m.containsNansOnly(fieldID) {
return rowsCannotMatch
}
- if s.Len() > inPredicateLimit {
- // skip evaluating the predicate if the number of values is too big
+ hasExtrema := minLit != nil && maxLit != nil
+ oversized := s.Len() > inPredicateLimit
+ if oversized && !hasExtrema {
+ // Skip evaluating the predicate if the number of values is too big.
return rowsMightMatch
}
- values := s.Members()
- if lowerBound, ok := m.boundFor(t, m.lowerBounds[fieldID]); ok {
+ var values []iceberg.Literal
+ lowerBound, hasLowerBound := m.boundFor(t, m.lowerBounds[fieldID])
+ if hasLowerBound {
if m.isNan(lowerBound) {
return rowsMightMatch
}
-
- values = removeBoundCheck(lowerBound, values, 1)
- if len(values) == 0 {
+ if hasExtrema && compareBoundLiterals(lowerBound, maxLit) > 0 {
+ // Short-circuit before decoding an unnecessary (possibly invalid) upper bound.
return rowsCannotMatch
}
+ if !hasExtrema {
+ // The slow path must finish the lower scan before reading the upper bound.
+ values = removeBoundCheck(lowerBound, s.Members(), 1)
+ if len(values) == 0 {
+ return rowsCannotMatch
+ }
+ }
}
- if upperBound, ok := m.boundFor(t, m.upperBounds[fieldID]); ok {
+ upperBound, hasUpperBound := m.boundFor(t, m.upperBounds[fieldID])
+ if hasUpperBound {
if m.isNan(upperBound) {
return rowsMightMatch
}
+ if hasExtrema && compareBoundLiterals(upperBound, minLit) < 0 {
+ return rowsCannotMatch
+ }
+ }
+
+ if oversized {
+ // Unlike Java's InclusiveEvalVisitor, we still prune disjoint oversized
Review Comment:
This closes the Java-divergence comment from last round, thanks. One wording thing: "the manifest evaluator handles its size limit in a separate branch" reads as if the manifest matches Java, but its `hasExtrema` branch prunes oversized sets the same way this one does. I'd reword to say both evaluators prune oversized IN sets on extrema, and drop the equivalent one-liner on the manifest branch so the two read consistently.
##########
table/evaluators.go:
##########
@@ -326,6 +330,52 @@ func getCmpLiteral(boundary iceberg.Literal) func(iceberg.Literal, iceberg.Liter
panic(iceberg.ErrType)
}
+// compareLiteralValues requires the same concrete literal type on both sides,
+// as guaranteed for bound predicates. A mismatched type assertion will panic.
+func compareLiteralValues[T iceberg.LiteralType](left, right iceberg.Literal) int {
+ leftValue := left.(iceberg.TypedLiteral[T])
+ rightValue := right.(iceberg.TypedLiteral[T])
+
+ return leftValue.Comparator()(leftValue.Value(), rightValue.Value())
+}
+
+// Keep this dispatch aligned with getCmpLiteral, removeBoundCheck, and
+// allBoundCheck when adding a new literal type.
+func compareBoundLiterals(left, right iceberg.Literal) int {
+ switch left.(type) {
+ case iceberg.TypedLiteral[bool]:
+ return compareLiteralValues[bool](left, right)
+ case iceberg.TypedLiteral[int32]:
+ return compareLiteralValues[int32](left, right)
+ case iceberg.TypedLiteral[int64]:
+ return compareLiteralValues[int64](left, right)
+ case iceberg.TypedLiteral[float32]:
+ return compareLiteralValues[float32](left, right)
+ case iceberg.TypedLiteral[float64]:
+ return compareLiteralValues[float64](left, right)
+ case iceberg.TypedLiteral[iceberg.Date]:
+ return compareLiteralValues[iceberg.Date](left, right)
+ case iceberg.TypedLiteral[iceberg.Time]:
+ return compareLiteralValues[iceberg.Time](left, right)
+ case iceberg.TypedLiteral[iceberg.Timestamp]:
+ return compareLiteralValues[iceberg.Timestamp](left, right)
+ case iceberg.TypedLiteral[iceberg.TimestampNano]:
+ return compareLiteralValues[iceberg.TimestampNano](left, right)
+ case iceberg.TypedLiteral[[]byte]:
+ return compareLiteralValues[[]byte](left, right)
+ case iceberg.TypedLiteral[string]:
+ return compareLiteralValues[string](left, right)
+ case iceberg.TypedLiteral[uuid.UUID]:
+ return compareLiteralValues[uuid.UUID](left, right)
+ case iceberg.TypedLiteral[iceberg.Decimal]:
+ return compareLiteralValues[iceberg.Decimal](left, right)
+ case iceberg.GeoLiteral:
Review Comment:
`TestVisitBoundPredicateRefGeoSkipsExtrema` covers the gating, so that item landed. This panic is only unreachable because that gating keeps geo off the extrema path, which is worth a one-line note here since the safety is otherwise implicit. The gating test also proves no extrema are passed but not that a real geo IN through `newInclusiveMetricsEvaluator` takes `VisitIn` rather than reaching this line; one end-to-end run would close that.
##########
table/in_predicate_extrema_test.go:
##########
@@ -139,6 +141,466 @@ func TestManifestEvaluatorInPredicateExtrema(t *testing.T) {
}
}
+func TestInclusiveMetricsEvaluatorInPredicateExtrema(t *testing.T) {
+ encode := func(value int32) []byte {
+ encoded, err := iceberg.NewLiteral(value).MarshalBinary()
+ require.NoError(t, err)
+
+ return encoded
+ }
+
+ schema := iceberg.NewSchema(1, iceberg.NestedField{ID: 1, Name: "value", Type: iceberg.PrimitiveTypes.Int32})
+ expr := iceberg.IsIn(iceberg.Reference("value"), int32(1), int32(100))
+ eval, err := newInclusiveMetricsEvaluator(schema, expr, true, true)
+ require.NoError(t, err)
+
+ tests := []struct {
+ name string
+ lowerBound []byte
+ upperBound []byte
+ want bool
+ }{
+ {name: "lower bound above set", lowerBound: encode(101), upperBound: encode(200), want: false},
+ {name: "upper bound below set", lowerBound: encode(-10), upperBound: encode(0), want: false},
+ {name: "sparse set has no member in range", lowerBound: encode(40), upperBound: encode(60), want: false},
+ {name: "overlapping range contains member", lowerBound: encode(50), upperBound: encode(100), want: true},
+ {name: "upper bound equals minimum literal", upperBound: encode(1), want: true},
+ {name: "lower bound equals maximum literal", lowerBound: encode(100), want: true},
+ {name: "missing bounds", want: true},
+ {name: "upper bound below set without lower bound", upperBound: encode(0), want: false},
+ {name: "lower bound above set without upper bound", lowerBound: encode(101), want: false},
+ {name: "disjoint lower bound avoids malformed upper bound", lowerBound: encode(101), upperBound: []byte{1}, want: false},
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ file := inclusiveMetricsInTestFile(t, tt.lowerBound, tt.upperBound)
+ got, err := eval(file)
+ require.NoError(t, err)
+ assert.Equal(t, tt.want, got)
+ })
+ }
+
+ t.Run("NaN bounds fail open", func(t *testing.T) {
+ encodeFloat := func(value float64) []byte {
+ encoded, err := iceberg.NewLiteral(value).MarshalBinary()
+ require.NoError(t, err)
+
+ return encoded
+ }
+ nan := encodeFloat(math.NaN())
+ finiteLower := encodeFloat(0)
+ finiteUpper := encodeFloat(3)
+ floatSchema := iceberg.NewSchema(1, iceberg.NestedField{
+ ID: 1, Name: "value", Type: iceberg.PrimitiveTypes.Float64,
+ })
+ floatEval, err := newInclusiveMetricsEvaluator(
+ floatSchema, iceberg.IsIn(iceberg.Reference("value"), float64(1), float64(2)), true, true,
+ )
+ require.NoError(t, err)
+
+ for _, bounds := range []struct {
+ name string
+ lower, upper []byte
+ }{
+ {name: "both NaN", lower: nan, upper: nan},
+ {name: "NaN lower finite upper", lower: nan, upper: finiteUpper},
+ {name: "finite lower NaN upper", lower: finiteLower, upper: nan},
+ } {
+ t.Run(bounds.name, func(t *testing.T) {
+ got, err := floatEval(inclusiveMetricsInTestFile(t, bounds.lower, bounds.upper))
+ require.NoError(t, err)
+ assert.True(t, got)
+ })
+ }
+ })
+
+ t.Run("oversized set still uses extrema before member scan limit", func(t *testing.T) {
+ values := make([]int32, inPredicateLimit+1)
+ for i := range values {
+ values[i] = int32(i)
+ }
+ largeEval, err := newInclusiveMetricsEvaluator(
+ schema, iceberg.IsIn(iceberg.Reference("value"), values...), true, true,
+ )
+ require.NoError(t, err)
+
+ disjointLower := int32(inPredicateLimit + 1000)
+ got, err := largeEval(inclusiveMetricsInTestFile(
+ t, encode(disjointLower), encode(disjointLower+1),
+ ))
+ require.NoError(t, err)
+ assert.False(t, got)
+
+ got, err = largeEval(inclusiveMetricsInTestFile(t, encode(50), encode(60)))
+ require.NoError(t, err)
+ assert.True(t, got)
+ })
+}
+
+func TestInclusiveMetricsEvaluatorInPredicateExtremaFastPathTypes(t *testing.T) {
+ decimal := func(value int64) iceberg.Decimal {
+ return iceberg.Decimal{Val: decimal128.FromI64(value), Scale: 2}
+ }
+
+ tests := []struct {
+ name string
+ typ iceberg.Type
+ expr iceberg.BooleanExpression
+ minLit, maxLit iceberg.Literal
+ lower, upper iceberg.Literal
+ want bool
+ }{
+ {
+ name: "string lower disjoint",
+ typ: iceberg.PrimitiveTypes.String,
+ expr: iceberg.IsIn(iceberg.Reference("value"), "a", "b"),
+ minLit: iceberg.NewLiteral("a"), maxLit: iceberg.NewLiteral("b"),
+ lower: iceberg.NewLiteral("m"), upper: iceberg.NewLiteral("z"),
+ },
+ {
+ name: "string overlaps",
+ typ: iceberg.PrimitiveTypes.String,
+ expr: iceberg.IsIn(iceberg.Reference("value"), "a", "b"),
+ minLit: iceberg.NewLiteral("a"), maxLit: iceberg.NewLiteral("b"),
+ lower: iceberg.NewLiteral("a"), upper: iceberg.NewLiteral("a"),
+ want: true,
+ },
+ {
+ name: "decimal upper disjoint",
+ typ: iceberg.DecimalTypeOf(12, 2),
+ expr: iceberg.IsIn(iceberg.Reference("value"), decimal(100), decimal(200)),
+ minLit: iceberg.NewLiteral(decimal(100)), maxLit: iceberg.NewLiteral(decimal(200)),
+ lower: iceberg.NewLiteral(decimal(-200)), upper: iceberg.NewLiteral(decimal(0)),
+ },
+ {
+ name: "decimal overlaps",
+ typ: iceberg.DecimalTypeOf(12, 2),
+ expr: iceberg.IsIn(iceberg.Reference("value"), decimal(100), decimal(200)),
+ minLit: iceberg.NewLiteral(decimal(100)), maxLit: iceberg.NewLiteral(decimal(200)),
+ lower: iceberg.NewLiteral(decimal(100)), upper: iceberg.NewLiteral(decimal(150)),
+ want: true,
+ },
+ {
+ name: "binary lower disjoint",
+ typ: iceberg.PrimitiveTypes.Binary,
+ expr: iceberg.IsIn(iceberg.Reference("value"), []byte{1}, []byte{2}),
+ minLit: iceberg.NewLiteral([]byte{1}), maxLit: iceberg.NewLiteral([]byte{2}),
+ lower: iceberg.NewLiteral([]byte{10}), upper: iceberg.NewLiteral([]byte{20}),
+ },
+ {
+ name: "binary overlaps",
+ typ: iceberg.PrimitiveTypes.Binary,
+ expr: iceberg.IsIn(iceberg.Reference("value"), []byte{1}, []byte{2}),
+ minLit: iceberg.NewLiteral([]byte{1}), maxLit: iceberg.NewLiteral([]byte{2}),
+ lower: iceberg.NewLiteral([]byte{1}), upper: iceberg.NewLiteral([]byte{1}),
+ want: true,
+ },
+ {
+ name: "date upper disjoint",
+ typ: iceberg.PrimitiveTypes.Date,
+ expr: iceberg.IsIn(iceberg.Reference("value"), iceberg.Date(10), iceberg.Date(20)),
+ minLit: iceberg.NewLiteral(iceberg.Date(10)), maxLit: iceberg.NewLiteral(iceberg.Date(20)),
+ lower: iceberg.NewLiteral(iceberg.Date(-10)), upper: iceberg.NewLiteral(iceberg.Date(0)),
+ },
+ {
+ name: "date overlaps",
+ typ: iceberg.PrimitiveTypes.Date,
+ expr: iceberg.IsIn(iceberg.Reference("value"), iceberg.Date(10), iceberg.Date(20)),
+ minLit: iceberg.NewLiteral(iceberg.Date(10)), maxLit: iceberg.NewLiteral(iceberg.Date(20)),
+ lower: iceberg.NewLiteral(iceberg.Date(10)), upper: iceberg.NewLiteral(iceberg.Date(15)),
+ want: true,
+ },
+ {
+ name: "timestamp lower disjoint",
+ typ: iceberg.PrimitiveTypes.Timestamp,
+ expr: iceberg.IsIn(iceberg.Reference("value"), iceberg.Timestamp(10), iceberg.Timestamp(20)),
+ minLit: iceberg.NewLiteral(iceberg.Timestamp(10)), maxLit: iceberg.NewLiteral(iceberg.Timestamp(20)),
+ lower: iceberg.NewLiteral(iceberg.Timestamp(30)), upper: iceberg.NewLiteral(iceberg.Timestamp(40)),
+ },
+ {
+ name: "timestamp overlaps",
+ typ: iceberg.PrimitiveTypes.Timestamp,
+ expr: iceberg.IsIn(iceberg.Reference("value"), iceberg.Timestamp(10), iceberg.Timestamp(20)),
+ minLit: iceberg.NewLiteral(iceberg.Timestamp(10)), maxLit: iceberg.NewLiteral(iceberg.Timestamp(20)),
+ lower: iceberg.NewLiteral(iceberg.Timestamp(10)), upper: iceberg.NewLiteral(iceberg.Timestamp(15)),
+ want: true,
+ },
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ schema := iceberg.NewSchema(1, iceberg.NestedField{ID: 1, Name: "value", Type: tt.typ})
+ bound, err := iceberg.BindExpr(schema, tt.expr, true)
+ require.NoError(t, err)
+ pred, ok := bound.(iceberg.BoundSetPredicate)
+ require.True(t, ok)
+
+ lower, err := tt.lower.MarshalBinary()
+ require.NoError(t, err)
+ upper, err := tt.upper.MarshalBinary()
+ require.NoError(t, err)
+ newVisitor := func() *inclusiveMetricsEval {
+ return &inclusiveMetricsEval{metricsEvaluator: metricsEvaluator{
+ valueCounts: map[int]int64{1: 10},
+ nullCounts: map[int]int64{1: 0},
+ nanCounts: map[int]int64{1: 0},
+ lowerBounds: map[int][]byte{1: lower},
+ upperBounds: map[int][]byte{1: upper},
+ }}
+ }
+
+ slow := newVisitor().VisitIn(pred.Term(), pred.Literals())
+ fast := newVisitor().VisitInWithExtrema(pred.Term(), pred.Literals(), tt.minLit, tt.maxLit)
+ require.Equal(t, slow, fast)
+ require.Equal(t, tt.want, fast)
+ })
+ }
+}
+
+type inExtremaTrackingSet struct {
+ iceberg.Set[iceberg.Literal]
+ memberCalls int
+}
+
+func (s *inExtremaTrackingSet) Members() []iceberg.Literal {
+ s.memberCalls++
+
+ return s.Set.Members()
+}
+
+func TestInclusiveMetricsEvaluatorInPredicateExtremaUsesFastPath(t *testing.T) {
+ decimal := func(value int64) iceberg.Decimal {
+ return iceberg.Decimal{Val: decimal128.FromI64(value), Scale: 2}
+ }
+ // Both paths must prune these disjoint files. The extrema path must do so
+ // without materializing the set members, using the actual bound extrema.
+ tests := []struct {
+ name string
+ typ iceberg.Type
+ bounds []iceberg.Literal
+ minLit, maxLit iceberg.Literal
+ }{
+ {
+ "string", iceberg.PrimitiveTypes.String,
+ []iceberg.Literal{iceberg.NewLiteral("m"), iceberg.NewLiteral("n")},
+ iceberg.NewLiteral("a"), iceberg.NewLiteral("b"),
+ },
+ {
+ "decimal", iceberg.DecimalTypeOf(12, 2),
+ []iceberg.Literal{iceberg.NewLiteral(decimal(5000)), iceberg.NewLiteral(decimal(6000))},
+ iceberg.NewLiteral(decimal(100)), iceberg.NewLiteral(decimal(200)),
+ },
+ {
+ "binary", iceberg.PrimitiveTypes.Binary,
+ []iceberg.Literal{iceberg.NewLiteral([]byte("m")), iceberg.NewLiteral([]byte("n"))},
+ iceberg.NewLiteral([]byte("a")), iceberg.NewLiteral([]byte("b")),
+ },
+ {
+ "date", iceberg.PrimitiveTypes.Date,
+ []iceberg.Literal{iceberg.NewLiteral(iceberg.Date(50)), iceberg.NewLiteral(iceberg.Date(60))},
+ iceberg.NewLiteral(iceberg.Date(1)), iceberg.NewLiteral(iceberg.Date(2)),
+ },
+ {
+ "timestamp", iceberg.PrimitiveTypes.Timestamp,
+ []iceberg.Literal{iceberg.NewLiteral(iceberg.Timestamp(50)), iceberg.NewLiteral(iceberg.Timestamp(60))},
+ iceberg.NewLiteral(iceberg.Timestamp(1)), iceberg.NewLiteral(iceberg.Timestamp(2)),
+ },
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ schema := iceberg.NewSchema(1, iceberg.NestedField{ID: 1, Name: "value", Type: tt.typ})
+ bound, err := iceberg.BindExpr(schema, iceberg.SetPredicate(
+ iceberg.OpIn, iceberg.Reference("value"), []iceberg.Literal{tt.minLit, tt.maxLit},
+ ), true)
+ require.NoError(t, err)
+ pred, ok := bound.(iceberg.BoundSetPredicate)
+ require.True(t, ok)
+
+ lower, err := tt.bounds[0].MarshalBinary()
+ require.NoError(t, err)
+ upper, err := tt.bounds[1].MarshalBinary()
+ require.NoError(t, err)
+ newVisitor := func() *inclusiveMetricsEval {
+ return &inclusiveMetricsEval{metricsEvaluator: metricsEvaluator{
+ valueCounts: map[int]int64{1: 10},
+ nullCounts: map[int]int64{1: 0},
+ nanCounts: map[int]int64{1: 0},
+ lowerBounds: map[int][]byte{1: lower},
+ upperBounds: map[int][]byte{1: upper},
+ }}
+ }
+
+ slowSet := &inExtremaTrackingSet{Set: pred.Literals()}
+ require.False(t, newVisitor().VisitIn(pred.Term(), slowSet))
+ require.Equal(t, 1, slowSet.memberCalls)
+
+ fastSet := &inExtremaTrackingSet{Set: pred.Literals()}
Review Comment:
This proves the member scan was skipped, which is the real improvement over last round, but every row still feeds the set's true extrema, so a regression that ignored the passed `minLit`/`maxLit` and recomputed from `s` would stay green. That's the lying-extrema case I flagged before. I'd add one row where the extrema deliberately disagree with the set (set `{1,100}`, file bounds `[50,60]`, passed extrema `(70,80)`) and assert the extrema-derived answer, and while you're here an overlap row asserting `memberCalls == 1` covers the non-prunable path these rows never reach.
--
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] perf(table): fast-path IN metrics pruning with extrema [iceberg-go]
Posted by "laskoviymishka (via GitHub)" <gi...@apache.org>.
laskoviymishka commented on code in PR #2117:
URL: https://github.com/apache/iceberg-go/pull/2117#discussion_r4208297528
##########
table/evaluators.go:
##########
@@ -1142,34 +1188,71 @@ func (m *inclusiveMetricsEval) VisitNotEqual(iceberg.BoundTerm, iceberg.Literal)
}
func (m *inclusiveMetricsEval) VisitIn(t iceberg.BoundTerm, s iceberg.Set[iceberg.Literal]) bool {
+ return m.visitIn(t, s, nil, nil)
+}
+
+// VisitInWithExtrema expects minLit and maxLit to either both be the actual
+// extrema of s or both be nil. A partial pair is treated as unavailable and
+// follows the same path as VisitIn.
+func (m *inclusiveMetricsEval) VisitInWithExtrema(
+ t iceberg.BoundTerm, s iceberg.Set[iceberg.Literal], minLit, maxLit iceberg.Literal,
+) bool {
+ return m.visitIn(t, s, minLit, maxLit)
+}
+
+func (m *inclusiveMetricsEval) visitIn(
+ t iceberg.BoundTerm, s iceberg.Set[iceberg.Literal], minLit, maxLit iceberg.Literal,
+) bool {
fieldID := t.Ref().Field().ID
if m.containsNullsOnly(fieldID) || m.containsNansOnly(fieldID) {
return rowsCannotMatch
}
- if s.Len() > inPredicateLimit {
- // skip evaluating the predicate if the number of values is too big
+ hasExtrema := minLit != nil && maxLit != nil
+ oversized := s.Len() > inPredicateLimit
+ if oversized && !hasExtrema {
+ // Skip evaluating the predicate if the number of values is too big.
return rowsMightMatch
}
- values := s.Members()
- if lowerBound, ok := m.boundFor(t, m.lowerBounds[fieldID]); ok {
+ lowerBound, hasLowerBound := m.boundFor(t, m.lowerBounds[fieldID])
+ if hasLowerBound {
if m.isNan(lowerBound) {
return rowsMightMatch
}
-
- values = removeBoundCheck(lowerBound, values, 1)
- if len(values) == 0 {
+ if hasExtrema && compareBoundLiterals(lowerBound, maxLit) > 0 {
+ // Preserve this lower-bound short circuit before decoding the upper
+ // bound: malformed upper metrics must not matter once lower proves
+ // the set disjoint.
return rowsCannotMatch
}
}
- if upperBound, ok := m.boundFor(t, m.upperBounds[fieldID]); ok {
+ upperBound, hasUpperBound := m.boundFor(t, m.upperBounds[fieldID])
+ if hasUpperBound {
if m.isNan(upperBound) {
return rowsMightMatch
}
+ if hasExtrema && compareBoundLiterals(upperBound, minLit) < 0 {
+ return rowsCannotMatch
+ }
+ }
+
+ if oversized {
Review Comment:
Worth expanding this comment to say it's a deliberate divergence from Java: Java bails to `ROWS_MIGHT_MATCH` as soon as the set crosses `IN_PREDICATE_LIMIT`, whereas we run the two O(1) extrema compares first and only cap the per-member scan. It's sound (rejecting when lower > max or upper < min is exactly the proof the non-oversized path makes, just cheaper, and it never drops a file that could match), but it does mean we return a different file set than Java for the same oversized IN, which is the kind of thing a future reader will trip on.
The manifest evaluator's `visitIn` doesn't take the oversized branch the same way, so the two evaluators aren't symmetric here either. Probably fine, but worth a line saying so. Diverging from Java's limit is the right call to me; I'd just make it legible in the comment so it reads as intentional.
##########
table/evaluators.go:
##########
@@ -1142,34 +1188,71 @@ func (m *inclusiveMetricsEval) VisitNotEqual(iceberg.BoundTerm, iceberg.Literal)
}
func (m *inclusiveMetricsEval) VisitIn(t iceberg.BoundTerm, s iceberg.Set[iceberg.Literal]) bool {
+ return m.visitIn(t, s, nil, nil)
+}
+
+// VisitInWithExtrema expects minLit and maxLit to either both be the actual
+// extrema of s or both be nil. A partial pair is treated as unavailable and
+// follows the same path as VisitIn.
+func (m *inclusiveMetricsEval) VisitInWithExtrema(
+ t iceberg.BoundTerm, s iceberg.Set[iceberg.Literal], minLit, maxLit iceberg.Literal,
+) bool {
+ return m.visitIn(t, s, minLit, maxLit)
+}
+
+func (m *inclusiveMetricsEval) visitIn(
+ t iceberg.BoundTerm, s iceberg.Set[iceberg.Literal], minLit, maxLit iceberg.Literal,
+) bool {
fieldID := t.Ref().Field().ID
if m.containsNullsOnly(fieldID) || m.containsNansOnly(fieldID) {
return rowsCannotMatch
}
- if s.Len() > inPredicateLimit {
- // skip evaluating the predicate if the number of values is too big
+ hasExtrema := minLit != nil && maxLit != nil
+ oversized := s.Len() > inPredicateLimit
+ if oversized && !hasExtrema {
+ // Skip evaluating the predicate if the number of values is too big.
return rowsMightMatch
}
- values := s.Members()
- if lowerBound, ok := m.boundFor(t, m.lowerBounds[fieldID]); ok {
+ lowerBound, hasLowerBound := m.boundFor(t, m.lowerBounds[fieldID])
+ if hasLowerBound {
if m.isNan(lowerBound) {
return rowsMightMatch
}
-
- values = removeBoundCheck(lowerBound, values, 1)
- if len(values) == 0 {
+ if hasExtrema && compareBoundLiterals(lowerBound, maxLit) > 0 {
+ // Preserve this lower-bound short circuit before decoding the upper
+ // bound: malformed upper metrics must not matter once lower proves
+ // the set disjoint.
return rowsCannotMatch
}
}
- if upperBound, ok := m.boundFor(t, m.upperBounds[fieldID]); ok {
+ upperBound, hasUpperBound := m.boundFor(t, m.upperBounds[fieldID])
Review Comment:
In the no-extrema path we now decode the upper bound and run its NaN check before the lower-bound member scan (`removeBoundCheck` further down). On main that scan ran first and returned `rowsCannotMatch` the moment the lower emptied the set, before `boundFor` ever touched the upper.
Two things fall out, both slow-path only (plain `VisitIn`, or a partial-nil extrema pair). A disjoint lower with a NaN upper used to prune and now returns `rowsMightMatch`. A disjoint lower with a malformed upper used to prune cleanly but now reaches `boundFor` and panics on the `LiteralFromBytes` failure. The fast path still keeps lower-before-upper, so fast and slow now disagree on exactly the inputs the "malformed upper metrics must not matter once lower proves the set disjoint" comment promises to protect, and that comment only holds when extrema are present. This is the descendant of the malformed-upper ordering caution from last round, so I'd like it closed before merge.
I'd finish the lower-side decision before fetching the upper in the `!hasExtrema` branch: run `removeBoundCheck(lower)` and the empty-check inside the lower block, then fetch the upper. A slow-path test (partial-nil extrema, or straight `VisitIn`) with a disjoint lower and a malformed `[]byte{1}` upper, plus one with a NaN upper, would pin it.
##########
table/in_predicate_extrema_test.go:
##########
@@ -139,6 +141,323 @@ func TestManifestEvaluatorInPredicateExtrema(t *testing.T) {
}
}
+func TestInclusiveMetricsEvaluatorInPredicateExtrema(t *testing.T) {
+ encode := func(value int32) []byte {
+ encoded, err := iceberg.NewLiteral(value).MarshalBinary()
+ require.NoError(t, err)
+
+ return encoded
+ }
+
+ schema := iceberg.NewSchema(1, iceberg.NestedField{ID: 1, Name: "value", Type: iceberg.PrimitiveTypes.Int32})
+ expr := iceberg.IsIn(iceberg.Reference("value"), int32(1), int32(100))
+ eval, err := newInclusiveMetricsEvaluator(schema, expr, true, true)
+ require.NoError(t, err)
+
+ tests := []struct {
+ name string
+ lowerBound []byte
+ upperBound []byte
+ want bool
+ }{
+ {name: "lower bound above set", lowerBound: encode(101), upperBound: encode(200), want: false},
+ {name: "upper bound below set", lowerBound: encode(-10), upperBound: encode(0), want: false},
+ {name: "sparse set has no member in range", lowerBound: encode(40), upperBound: encode(60), want: false},
+ {name: "overlapping range contains member", lowerBound: encode(50), upperBound: encode(100), want: true},
+ {name: "upper bound equals minimum literal", upperBound: encode(1), want: true},
+ {name: "lower bound equals maximum literal", lowerBound: encode(100), want: true},
+ {name: "missing bounds", want: true},
+ {name: "upper bound below set without lower bound", upperBound: encode(0), want: false},
+ {name: "lower bound above set without upper bound", lowerBound: encode(101), want: false},
+ {name: "disjoint lower bound avoids malformed upper bound", lowerBound: encode(101), upperBound: []byte{1}, want: false},
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ file := inclusiveMetricsInTestFile(t, tt.lowerBound, tt.upperBound)
+ got, err := eval(file)
+ require.NoError(t, err)
+ assert.Equal(t, tt.want, got)
+ })
+ }
+
+ t.Run("NaN bounds fail open", func(t *testing.T) {
+ encodeFloat := func(value float64) []byte {
+ encoded, err := iceberg.NewLiteral(value).MarshalBinary()
+ require.NoError(t, err)
+
+ return encoded
+ }
+ nan := encodeFloat(math.NaN())
+ finiteLower := encodeFloat(0)
+ finiteUpper := encodeFloat(3)
+ floatSchema := iceberg.NewSchema(1, iceberg.NestedField{
+ ID: 1, Name: "value", Type: iceberg.PrimitiveTypes.Float64,
+ })
+ floatEval, err := newInclusiveMetricsEvaluator(
+ floatSchema, iceberg.IsIn(iceberg.Reference("value"), float64(1), float64(2)), true, true,
+ )
+ require.NoError(t, err)
+
+ for _, bounds := range []struct {
+ name string
+ lower, upper []byte
+ }{
+ {name: "both NaN", lower: nan, upper: nan},
+ {name: "NaN lower finite upper", lower: nan, upper: finiteUpper},
+ {name: "finite lower NaN upper", lower: finiteLower, upper: nan},
+ } {
+ t.Run(bounds.name, func(t *testing.T) {
+ got, err := floatEval(inclusiveMetricsInTestFile(t, bounds.lower, bounds.upper))
+ require.NoError(t, err)
+ assert.True(t, got)
+ })
+ }
+ })
+
+ t.Run("oversized set still uses extrema before member scan limit", func(t *testing.T) {
+ values := make([]int32, inPredicateLimit+1)
+ for i := range values {
+ values[i] = int32(i)
+ }
+ largeEval, err := newInclusiveMetricsEvaluator(
+ schema, iceberg.IsIn(iceberg.Reference("value"), values...), true, true,
+ )
+ require.NoError(t, err)
+
+ disjointLower := int32(inPredicateLimit + 1000)
+ got, err := largeEval(inclusiveMetricsInTestFile(
+ t, encode(disjointLower), encode(disjointLower+1),
+ ))
+ require.NoError(t, err)
+ assert.False(t, got)
+
+ got, err = largeEval(inclusiveMetricsInTestFile(t, encode(50), encode(60)))
+ require.NoError(t, err)
+ assert.True(t, got)
+ })
+}
+
+func TestInclusiveMetricsEvaluatorInPredicateExtremaFastPathTypes(t *testing.T) {
+ decimal := func(value int64) iceberg.Decimal {
+ return iceberg.Decimal{Val: decimal128.FromI64(value), Scale: 2}
+ }
+
+ tests := []struct {
+ name string
+ typ iceberg.Type
+ expr iceberg.BooleanExpression
+ minLit, maxLit iceberg.Literal
+ lower, upper iceberg.Literal
+ want bool
+ }{
+ {
+ name: "string lower disjoint",
+ typ: iceberg.PrimitiveTypes.String,
+ expr: iceberg.IsIn(iceberg.Reference("value"), "a", "b"),
+ minLit: iceberg.NewLiteral("a"), maxLit: iceberg.NewLiteral("b"),
+ lower: iceberg.NewLiteral("m"), upper: iceberg.NewLiteral("z"),
+ },
+ {
+ name: "string overlaps",
+ typ: iceberg.PrimitiveTypes.String,
+ expr: iceberg.IsIn(iceberg.Reference("value"), "a", "b"),
+ minLit: iceberg.NewLiteral("a"), maxLit: iceberg.NewLiteral("b"),
+ lower: iceberg.NewLiteral("a"), upper: iceberg.NewLiteral("a"),
+ want: true,
+ },
+ {
+ name: "decimal upper disjoint",
+ typ: iceberg.DecimalTypeOf(12, 2),
+ expr: iceberg.IsIn(iceberg.Reference("value"), decimal(100), decimal(200)),
+ minLit: iceberg.NewLiteral(decimal(100)), maxLit: iceberg.NewLiteral(decimal(200)),
+ lower: iceberg.NewLiteral(decimal(-200)), upper: iceberg.NewLiteral(decimal(0)),
+ },
+ {
+ name: "decimal overlaps",
+ typ: iceberg.DecimalTypeOf(12, 2),
+ expr: iceberg.IsIn(iceberg.Reference("value"), decimal(100), decimal(200)),
+ minLit: iceberg.NewLiteral(decimal(100)), maxLit: iceberg.NewLiteral(decimal(200)),
+ lower: iceberg.NewLiteral(decimal(100)), upper: iceberg.NewLiteral(decimal(150)),
+ want: true,
+ },
+ {
+ name: "binary lower disjoint",
+ typ: iceberg.PrimitiveTypes.Binary,
+ expr: iceberg.IsIn(iceberg.Reference("value"), []byte{1}, []byte{2}),
+ minLit: iceberg.NewLiteral([]byte{1}), maxLit: iceberg.NewLiteral([]byte{2}),
+ lower: iceberg.NewLiteral([]byte{10}), upper: iceberg.NewLiteral([]byte{20}),
+ },
+ {
+ name: "binary overlaps",
+ typ: iceberg.PrimitiveTypes.Binary,
+ expr: iceberg.IsIn(iceberg.Reference("value"), []byte{1}, []byte{2}),
+ minLit: iceberg.NewLiteral([]byte{1}), maxLit: iceberg.NewLiteral([]byte{2}),
+ lower: iceberg.NewLiteral([]byte{1}), upper: iceberg.NewLiteral([]byte{1}),
+ want: true,
+ },
+ {
+ name: "date upper disjoint",
+ typ: iceberg.PrimitiveTypes.Date,
+ expr: iceberg.IsIn(iceberg.Reference("value"), iceberg.Date(10), iceberg.Date(20)),
+ minLit: iceberg.NewLiteral(iceberg.Date(10)), maxLit: iceberg.NewLiteral(iceberg.Date(20)),
+ lower: iceberg.NewLiteral(iceberg.Date(-10)), upper: iceberg.NewLiteral(iceberg.Date(0)),
+ },
+ {
+ name: "date overlaps",
+ typ: iceberg.PrimitiveTypes.Date,
+ expr: iceberg.IsIn(iceberg.Reference("value"), iceberg.Date(10), iceberg.Date(20)),
+ minLit: iceberg.NewLiteral(iceberg.Date(10)), maxLit: iceberg.NewLiteral(iceberg.Date(20)),
+ lower: iceberg.NewLiteral(iceberg.Date(10)), upper: iceberg.NewLiteral(iceberg.Date(15)),
+ want: true,
+ },
+ {
+ name: "timestamp lower disjoint",
+ typ: iceberg.PrimitiveTypes.Timestamp,
+ expr: iceberg.IsIn(iceberg.Reference("value"), iceberg.Timestamp(10), iceberg.Timestamp(20)),
+ minLit: iceberg.NewLiteral(iceberg.Timestamp(10)), maxLit: iceberg.NewLiteral(iceberg.Timestamp(20)),
+ lower: iceberg.NewLiteral(iceberg.Timestamp(30)), upper: iceberg.NewLiteral(iceberg.Timestamp(40)),
+ },
+ {
+ name: "timestamp overlaps",
+ typ: iceberg.PrimitiveTypes.Timestamp,
+ expr: iceberg.IsIn(iceberg.Reference("value"), iceberg.Timestamp(10), iceberg.Timestamp(20)),
+ minLit: iceberg.NewLiteral(iceberg.Timestamp(10)), maxLit: iceberg.NewLiteral(iceberg.Timestamp(20)),
+ lower: iceberg.NewLiteral(iceberg.Timestamp(10)), upper: iceberg.NewLiteral(iceberg.Timestamp(15)),
+ want: true,
+ },
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ schema := iceberg.NewSchema(1, iceberg.NestedField{ID: 1, Name: "value", Type: tt.typ})
+ bound, err := iceberg.BindExpr(schema, tt.expr, true)
+ require.NoError(t, err)
+ pred, ok := bound.(iceberg.BoundSetPredicate)
+ require.True(t, ok)
+
+ lower, err := tt.lower.MarshalBinary()
+ require.NoError(t, err)
+ upper, err := tt.upper.MarshalBinary()
+ require.NoError(t, err)
+ newVisitor := func() *inclusiveMetricsEval {
+ return &inclusiveMetricsEval{metricsEvaluator: metricsEvaluator{
+ valueCounts: map[int]int64{1: 10},
+ nullCounts: map[int]int64{1: 0},
+ nanCounts: map[int]int64{1: 0},
+ lowerBounds: map[int][]byte{1: lower},
+ upperBounds: map[int][]byte{1: upper},
+ }}
+ }
+
+ slow := newVisitor().VisitIn(pred.Term(), pred.Literals())
+ fast := newVisitor().VisitInWithExtrema(pred.Term(), pred.Literals(), tt.minLit, tt.maxLit)
+ require.Equal(t, slow, fast)
Review Comment:
These `slow == fast == want` cases prove the two paths agree, but they don't prove the extrema block is what produced the answer. Delete the fast-path block and the per-member scan computes the same result, so they stay green. This is the "prove the fast path actually fires" point from last round; right now the oversized-disjoint case and the malformed-upper case are the only two that genuinely exercise it, and both are int32.
I'd add a case per type where the set and the passed `minLit`/`maxLit` deliberately disagree, e.g. set `{50}` with extrema `(1, 2)` and bounds `40..60`, where the real members say might-match but a lying extrema pair forces a prune, and assert the result follows the extrema. That turns these into path-taken tests instead of differential ones.
##########
table/evaluators.go:
##########
@@ -326,6 +330,48 @@ func getCmpLiteral(boundary iceberg.Literal) func(iceberg.Literal, iceberg.Liter
panic(iceberg.ErrType)
}
+func compareLiteralValues[T iceberg.LiteralType](left, right iceberg.Literal) int {
Review Comment:
This is a fourth copy of the literal type-switch alongside `removeBoundCheck`, `allBoundCheck`, and `getCmpLiteral`, and they key on different things (`Type()` vs. the Go generic type), so adding a literal type means touching all four or a missed arm panics with a bare `ErrType` at scan time. Not blocking, but a `// keep in sync with getCmpLiteral` cross-reference, or routing one through the other, would save a future foot-gun.
On the allocation question zeroshade raised: calling `Comparator()` directly instead of `getCmpLiteral`'s captured closure is the right move, and for int/float/string/date/timestamp the comparator is a static func value with no per-call alloc. I didn't confirm binary/uuid/decimal aren't capturing, and the benchmark only reports allocs for int32, so string and decimal variants would close it out. While we're here, a one-line note on `compareLiteralValues` that left and right must be the same literal type would help, since the unchecked assertion panics rather than fails open on a mismatch.
--
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] perf(table): fast-path IN metrics pruning with extrema [iceberg-go]
Posted by "zeroshade (via GitHub)" <gi...@apache.org>.
zeroshade commented on code in PR #2117:
URL: https://github.com/apache/iceberg-go/pull/2117#discussion_r4198576048
##########
table/in_predicate_extrema_test.go:
##########
@@ -139,6 +141,279 @@ func TestManifestEvaluatorInPredicateExtrema(t *testing.T) {
}
}
+func TestInclusiveMetricsEvaluatorInPredicateExtrema(t *testing.T) {
+ encode := func(value int32) []byte {
+ encoded, err := iceberg.NewLiteral(value).MarshalBinary()
+ require.NoError(t, err)
+
+ return encoded
+ }
+
+ schema := iceberg.NewSchema(1, iceberg.NestedField{ID: 1, Name: "value", Type: iceberg.PrimitiveTypes.Int32})
+ expr := iceberg.IsIn(iceberg.Reference("value"), int32(1), int32(100))
+ eval, err := newInclusiveMetricsEvaluator(schema, expr, true, true)
+ require.NoError(t, err)
+
+ tests := []struct {
+ name string
+ lowerBound []byte
+ upperBound []byte
+ want bool
+ }{
+ {name: "lower bound above set", lowerBound: encode(101), upperBound: encode(200), want: false},
+ {name: "upper bound below set", lowerBound: encode(-10), upperBound: encode(0), want: false},
+ {name: "sparse set has no member in range", lowerBound: encode(40), upperBound: encode(60), want: false},
+ {name: "overlapping range contains member", lowerBound: encode(50), upperBound: encode(100), want: true},
+ {name: "upper bound equals minimum literal", upperBound: encode(1), want: true},
+ {name: "lower bound equals maximum literal", lowerBound: encode(100), want: true},
+ {name: "missing bounds", want: true},
+ {name: "upper bound below set without lower bound", upperBound: encode(0), want: false},
+ {name: "lower bound above set without upper bound", lowerBound: encode(101), want: false},
+ {name: "disjoint lower bound avoids malformed upper bound", lowerBound: encode(101), upperBound: []byte{1}, want: false},
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ file := inclusiveMetricsInTestFile(t, tt.lowerBound, tt.upperBound)
+ got, err := eval(file)
+ require.NoError(t, err)
+ assert.Equal(t, tt.want, got)
+ })
+ }
+
+ t.Run("NaN bounds fail open", func(t *testing.T) {
+ encodeFloat := func(value float64) []byte {
+ encoded, err := iceberg.NewLiteral(value).MarshalBinary()
+ require.NoError(t, err)
+
+ return encoded
+ }
+ nan := encodeFloat(math.NaN())
+ finiteLower := encodeFloat(0)
+ finiteUpper := encodeFloat(3)
+ floatSchema := iceberg.NewSchema(1, iceberg.NestedField{
+ ID: 1, Name: "value", Type: iceberg.PrimitiveTypes.Float64,
+ })
+ floatEval, err := newInclusiveMetricsEvaluator(
+ floatSchema, iceberg.IsIn(iceberg.Reference("value"), float64(1), float64(2)), true, true,
+ )
+ require.NoError(t, err)
+
+ for _, bounds := range []struct {
+ name string
+ lower, upper []byte
+ }{
+ {name: "both NaN", lower: nan, upper: nan},
+ {name: "NaN lower finite upper", lower: nan, upper: finiteUpper},
+ {name: "finite lower NaN upper", lower: finiteLower, upper: nan},
+ } {
+ t.Run(bounds.name, func(t *testing.T) {
+ got, err := floatEval(inclusiveMetricsInTestFile(t, bounds.lower, bounds.upper))
+ require.NoError(t, err)
+ assert.True(t, got)
+ })
+ }
+ })
+
+ t.Run("oversized set keeps existing fallback", func(t *testing.T) {
+ values := make([]int32, inPredicateLimit+1)
+ for i := range values {
+ values[i] = int32(i)
+ }
+ largeEval, err := newInclusiveMetricsEvaluator(
+ schema, iceberg.IsIn(iceberg.Reference("value"), values...), true, true,
+ )
+ require.NoError(t, err)
+
+ disjointLower := int32(inPredicateLimit + 1000)
+ got, err := largeEval(inclusiveMetricsInTestFile(
+ t, encode(disjointLower), encode(disjointLower+1),
+ ))
+ require.NoError(t, err)
+ assert.True(t, got)
Review Comment:
This now pins the size guard, but nothing in `table` checks that `inclusiveMetricsEval` takes the fast path at all. When I routed `VisitBound` through `iceberg.VisitBoundPredicate`, which never calls `VisitInWithExtrema`, the full `./table` suite still passed. The direct `VisitInWithExtrema` calls only test the method on its own, and the dispatch test lives in `iceberg`. So if the unexported `boundSetExtremaExprVisitor` signature drifts, or `VisitBound` changes, the optimization would disappear without any test failing. That is the part of `@laskoviymishka`'s test request that's still open. The manifest evaluator is covered by `large IN below lower bound` because its extrema check runs before `inPredicateLimit`. Doing the same here costs O(1) per file. It also lets IN lists over 200 values prune data files by their bounds (today they get no metrics pruning), and lets this subtest assert `false`, which checks the dispatch end to end. If you'd rather keep the guard first to match Ja
va's `InclusiveEvalVisitor.in`, that's reasonable, but then the path-taken check needs another assertion at the evaluator level.
##########
table/evaluators.go:
##########
@@ -1153,23 +1174,57 @@ func (m *inclusiveMetricsEval) VisitIn(t iceberg.BoundTerm, s iceberg.Set[iceber
return rowsMightMatch
}
- values := s.Members()
- if lowerBound, ok := m.boundFor(t, m.lowerBounds[fieldID]); ok {
+ hasExtrema := minLit != nil && maxLit != nil
+ var extremaCmp func(iceberg.Literal, iceberg.Literal) int
+ if hasExtrema {
+ extremaCmp = getCmpLiteral(minLit)
+ }
+
+ lowerBound, hasLowerBound := m.boundFor(t, m.lowerBounds[fieldID])
+ if hasLowerBound {
if m.isNan(lowerBound) {
return rowsMightMatch
}
+ if hasExtrema && extremaCmp(lowerBound, maxLit) > 0 {
+ // Preserve this lower-bound short circuit before decoding the upper
+ // bound: malformed upper metrics must not matter once lower proves
+ // the set disjoint.
+ return rowsCannotMatch
+ }
+ }
+
+ var (
+ upperBound iceberg.Literal
+ hasUpperBound bool
+ )
+ if hasExtrema {
+ upperBound, hasUpperBound = m.boundFor(t, m.upperBounds[fieldID])
+ if hasUpperBound {
+ if m.isNan(upperBound) {
+ return rowsMightMatch
+ }
+ if extremaCmp(upperBound, minLit) < 0 {
+ return rowsCannotMatch
+ }
+ }
+ }
+ values := s.Members()
+ if hasLowerBound {
values = removeBoundCheck(lowerBound, values, 1)
if len(values) == 0 {
return rowsCannotMatch
}
}
- if upperBound, ok := m.boundFor(t, m.upperBounds[fieldID]); ok {
- if m.isNan(upperBound) {
+ if !hasExtrema {
+ upperBound, hasUpperBound = m.boundFor(t, m.upperBounds[fieldID])
+ if hasUpperBound && m.isNan(upperBound) {
return rowsMightMatch
}
+ }
Review Comment:
On the straighten-`visitIn` thread: this second fetch exists only so that the `!hasExtrema` path decodes the upper bound after the lower scan. Through `Eval` and `TestRowGroup`, that path is only reachable for geometry/geography sets, because every orderable set gets extrema when it is bound. For geo sets, `removeBoundCheck` panics on any bound anyway. You can declare `upperBound, hasUpperBound := m.boundFor(...)` once, right after the lower block, followed by the NaN check and `if hasExtrema && extremaCmp(upperBound, minLit) < 0`. That gives the single flow `@laskoviymishka` asked for without changing any reachable result. I tried that shape and the full `./table` suite passes, including `disjoint lower bound avoids malformed upper bound`. Up to you and `@laskoviymishka`; not blocking.
##########
table/evaluators.go:
##########
@@ -1153,23 +1174,57 @@ func (m *inclusiveMetricsEval) VisitIn(t iceberg.BoundTerm, s iceberg.Set[iceber
return rowsMightMatch
}
- values := s.Members()
- if lowerBound, ok := m.boundFor(t, m.lowerBounds[fieldID]); ok {
+ hasExtrema := minLit != nil && maxLit != nil
+ var extremaCmp func(iceberg.Literal, iceberg.Literal) int
+ if hasExtrema {
+ extremaCmp = getCmpLiteral(minLit)
+ }
Review Comment:
`getCmpLiteral` returns the closure built in `getCmp`, and that closure escapes (`go build -gcflags=-m ./table` reports `func literal escapes to heap` at evaluators.go:292). Because it is built up front, every file evaluated against an IN predicate now pays a 24-byte heap allocation. That includes files that fall through to the member scan and files with no bounds for the column. Compared with `main` (Go 1.27.1, darwin/arm64, `GOMAXPROCS=1`, n=6, benchstat): in=10/overlap goes from 20k to 30k allocs/op and is 6.6% slower; in=10/sparse-gap is 5.0% slower (p=0.002); in=200/overlap goes from 30k to 40k allocs/op. below-set stays at 40k allocs/op, where `52e7e97` (the commit the description's table was measured at) had 30k. The `compareBoundLiterals` helper removed in `c477a9e` compared values without building a closure, and it matched `main` on overlap, so bringing it back (or any compare that doesn't return a func value) fixes this. Please refresh the table in the description at hea
d afterwards.
##########
bound_set_extrema_test.go:
##########
@@ -0,0 +1,115 @@
+// 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 iceberg
+
+import (
+ "encoding/binary"
+ "math"
+ "testing"
+
+ iceberginternal "github.com/apache/iceberg-go/internal"
+ "github.com/stretchr/testify/require"
+)
+
+func TestBoundSetExtremaUnavailableForGeoLiterals(t *testing.T) {
+ geoBytes := func(x, y float64) []byte {
+ data := make([]byte, 16)
+ binary.LittleEndian.PutUint64(data[:8], math.Float64bits(x))
+ binary.LittleEndian.PutUint64(data[8:], math.Float64bits(y))
+
+ return data
+ }
+
+ for _, tt := range []struct {
+ name string
+ typ Type
+ }{
+ {name: "geometry", typ: GeometryType{}},
+ {name: "geography", typ: GeographyType{}},
+ } {
+ t.Run(tt.name, func(t *testing.T) {
+ first, err := LiteralFromBytes(tt.typ, geoBytes(1, 2))
+ require.NoError(t, err)
+ second, err := LiteralFromBytes(tt.typ, geoBytes(3, 4))
+ require.NoError(t, err)
+
+ schema := NewSchema(1, NestedField{ID: 1, Name: "geo", Type: tt.typ})
+ bound, err := BindExpr(
+ schema,
+ SetPredicate(OpIn, Reference("geo"), []Literal{first, second}),
+ true,
+ )
+ require.NoError(t, err)
+ pred, ok := bound.(BoundPredicate)
+ require.True(t, ok)
+ extrema, ok := pred.(boundSetExtremaRef)
+ require.True(t, ok)
+
+ minLit, maxLit, hasExtrema := extrema.boundSetExtremaRef()
+ require.False(t, hasExtrema)
+ require.Nil(t, minLit)
+ require.Nil(t, maxLit)
+ })
+ }
+}
+
+type extremaDispatchProbe struct {
+ BoundBooleanExprVisitor[bool]
+ visitedIn bool
+ visitedExtrema bool
+ minLit Literal
+ maxLit Literal
+}
+
+func (v *extremaDispatchProbe) VisitIn(BoundTerm, Set[Literal]) bool {
+ v.visitedIn = true
+
+ return false
+}
+
+func (v *extremaDispatchProbe) VisitInWithExtrema(_ BoundTerm, _ Set[Literal], minLit, maxLit Literal) bool {
+ v.visitedExtrema = true
+ v.minLit = minLit
+ v.maxLit = maxLit
+
+ return true
+}
+
+func TestVisitBoundPredicateRefDispatchesSetExtrema(t *testing.T) {
Review Comment:
`TestVisitBoundPredicateRefPassesInExtrema` in `bound_set_extrema_internal_test.go` already checks this: the borrowed dispatch passes the extrema to `VisitInWithExtrema`, and `VisitBoundPredicate` falls back to `VisitIn`. `TestLiteralSetExtrema/geo has no ordering` covers the geo case one level down. I'd drop this test. If you want the geo check at bind time, add it to that existing internal test file rather than a second file for the same unit.
##########
table/in_predicate_extrema_test.go:
##########
@@ -139,6 +141,279 @@ func TestManifestEvaluatorInPredicateExtrema(t *testing.T) {
}
}
+func TestInclusiveMetricsEvaluatorInPredicateExtrema(t *testing.T) {
+ encode := func(value int32) []byte {
+ encoded, err := iceberg.NewLiteral(value).MarshalBinary()
+ require.NoError(t, err)
+
+ return encoded
+ }
+
+ schema := iceberg.NewSchema(1, iceberg.NestedField{ID: 1, Name: "value", Type: iceberg.PrimitiveTypes.Int32})
+ expr := iceberg.IsIn(iceberg.Reference("value"), int32(1), int32(100))
+ eval, err := newInclusiveMetricsEvaluator(schema, expr, true, true)
+ require.NoError(t, err)
+
+ tests := []struct {
+ name string
+ lowerBound []byte
+ upperBound []byte
+ want bool
+ }{
+ {name: "lower bound above set", lowerBound: encode(101), upperBound: encode(200), want: false},
+ {name: "upper bound below set", lowerBound: encode(-10), upperBound: encode(0), want: false},
+ {name: "sparse set has no member in range", lowerBound: encode(40), upperBound: encode(60), want: false},
+ {name: "overlapping range contains member", lowerBound: encode(50), upperBound: encode(100), want: true},
+ {name: "upper bound equals minimum literal", upperBound: encode(1), want: true},
+ {name: "lower bound equals maximum literal", lowerBound: encode(100), want: true},
+ {name: "missing bounds", want: true},
+ {name: "upper bound below set without lower bound", upperBound: encode(0), want: false},
+ {name: "lower bound above set without upper bound", lowerBound: encode(101), want: false},
+ {name: "disjoint lower bound avoids malformed upper bound", lowerBound: encode(101), upperBound: []byte{1}, want: false},
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ file := inclusiveMetricsInTestFile(t, tt.lowerBound, tt.upperBound)
+ got, err := eval(file)
+ require.NoError(t, err)
+ assert.Equal(t, tt.want, got)
+ })
+ }
+
+ t.Run("NaN bounds fail open", func(t *testing.T) {
+ encodeFloat := func(value float64) []byte {
+ encoded, err := iceberg.NewLiteral(value).MarshalBinary()
+ require.NoError(t, err)
+
+ return encoded
+ }
+ nan := encodeFloat(math.NaN())
+ finiteLower := encodeFloat(0)
+ finiteUpper := encodeFloat(3)
+ floatSchema := iceberg.NewSchema(1, iceberg.NestedField{
+ ID: 1, Name: "value", Type: iceberg.PrimitiveTypes.Float64,
+ })
+ floatEval, err := newInclusiveMetricsEvaluator(
+ floatSchema, iceberg.IsIn(iceberg.Reference("value"), float64(1), float64(2)), true, true,
+ )
+ require.NoError(t, err)
+
+ for _, bounds := range []struct {
+ name string
+ lower, upper []byte
+ }{
+ {name: "both NaN", lower: nan, upper: nan},
+ {name: "NaN lower finite upper", lower: nan, upper: finiteUpper},
+ {name: "finite lower NaN upper", lower: finiteLower, upper: nan},
+ } {
+ t.Run(bounds.name, func(t *testing.T) {
+ got, err := floatEval(inclusiveMetricsInTestFile(t, bounds.lower, bounds.upper))
+ require.NoError(t, err)
+ assert.True(t, got)
+ })
+ }
+ })
+
+ t.Run("oversized set keeps existing fallback", func(t *testing.T) {
+ values := make([]int32, inPredicateLimit+1)
+ for i := range values {
+ values[i] = int32(i)
+ }
+ largeEval, err := newInclusiveMetricsEvaluator(
+ schema, iceberg.IsIn(iceberg.Reference("value"), values...), true, true,
+ )
+ require.NoError(t, err)
+
+ disjointLower := int32(inPredicateLimit + 1000)
+ got, err := largeEval(inclusiveMetricsInTestFile(
+ t, encode(disjointLower), encode(disjointLower+1),
+ ))
+ require.NoError(t, err)
+ assert.True(t, got)
+ })
+}
+
+func TestInclusiveMetricsEvaluatorInPredicateExtremaFastPathTypes(t *testing.T) {
+ decimal := func(value int64) iceberg.Decimal {
+ return iceberg.Decimal{Val: decimal128.FromI64(value), Scale: 2}
+ }
+
+ tests := []struct {
+ name string
+ typ iceberg.Type
+ expr iceberg.BooleanExpression
+ minLit, maxLit iceberg.Literal
+ lower, upper iceberg.Literal
+ want bool
Review Comment:
Every row here is disjoint and leaves `want` at its zero value, so `slow == fast` only checks the case where the file is pruned. Adding one overlapping row per type with `want: true` would let it catch a type-specific over-prune, which is the direction that drops rows.
--
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] perf(table): fast-path IN metrics pruning with extrema [iceberg-go]
Posted by "laskoviymishka (via GitHub)" <gi...@apache.org>.
laskoviymishka commented on code in PR #2117:
URL: https://github.com/apache/iceberg-go/pull/2117#discussion_r4193441068
##########
table/in_predicate_extrema_test.go:
##########
@@ -139,6 +140,107 @@ func TestManifestEvaluatorInPredicateExtrema(t *testing.T) {
}
}
+func TestInclusiveMetricsEvaluatorInPredicateExtrema(t *testing.T) {
+ encode := func(value int32) []byte {
+ encoded, err := iceberg.NewLiteral(value).MarshalBinary()
+ require.NoError(t, err)
+
+ return encoded
+ }
+
+ schema := iceberg.NewSchema(1, iceberg.NestedField{ID: 1, Name: "value", Type: iceberg.PrimitiveTypes.Int32})
+ expr := iceberg.IsIn(iceberg.Reference("value"), int32(1), int32(100))
Review Comment:
The set here is int32-only, so nothing exercises `getCmpLiteral(minLit)` on the types where it matters: string, decimal, binary, date/timestamp, and especially the variant `BoundExtract` and geo literals where `getCmpLiteral` panics on an unrecognized type. I'd add a table-driven case running a few of those through the fast path.
Separately, none of these cases prove the extrema path is even taken, since every one returns the same answer through the slow `removeBoundCheck`. A regression in `boundSetExtremaRef` or the dispatcher would leave the whole suite green. I'd either call `VisitInWithExtrema` directly with explicit min/max in at least one case, or assert both entry points agree across the matrix the way the manifest test does.
##########
table/evaluators.go:
##########
@@ -1153,8 +1165,38 @@ func (m *inclusiveMetricsEval) VisitIn(t iceberg.BoundTerm, s iceberg.Set[iceber
return rowsMightMatch
}
- values := s.Members()
- if lowerBound, ok := m.boundFor(t, m.lowerBounds[fieldID]); ok {
+ hasExtrema := minLit != nil && maxLit != nil
+ var (
+ values []iceberg.Literal
+ lowerBound, upperBound iceberg.Literal
+ hasLowerBound bool
+ hasUpperBound bool
+ )
+ if hasExtrema {
Review Comment:
I'd fetch both bounds once up top and gate the extrema prune in a single `if hasExtrema` block, then fall through to the unchanged `Members()` and `removeBoundCheck` tail. Right now the lower-bound NaN check and the `boundFor` fetch are duplicated across the `hasExtrema` and `else` branches, and `hasExtrema` gets tested a second time further down to decide whether to re-fetch the upper bound, so any future change to bound handling has to land in three places and the two paths are easy to drift apart.
One thing to preserve: the current order means a lower-bound prune returns before the upper `boundFor` ever runs, and the `disjoint lower bound avoids malformed upper bound` test leans on exactly that. If we hoist the upper fetch to the top, that test's malformed `[]byte{1}` upper would now get decoded. So either keep the extrema prune ordered lower-then-upper so the short-circuit still skips the upper fetch, or pull the shared tail into a small `prunedByExtrema(t, fieldID, minLit, maxLit) bool` helper that leaves the existing body untouched. Either's fine, but I'd rather not have the fast path spliced into the middle of the old flow.
##########
table/in_predicate_extrema_bench_test.go:
##########
@@ -116,3 +119,93 @@ func benchmarkManifestIn[T iceberg.LiteralType](b *testing.B, values []T, lower,
manifestInPredicateBenchmarkSink = matched
}
}
+
+func BenchmarkInclusiveMetricsEvalInPredicate(b *testing.B) {
+ for _, literalCount := range []int{10, 50, 200} {
+ values := make([]int32, literalCount)
+ for i := range values {
+ values[i] = int32(i * 2)
+ }
+
+ maxValue := values[len(values)-1]
+ for _, bounds := range []struct {
+ name string
+ lower int32
+ upper int32
+ }{
+ {name: "below-set", lower: -2, upper: -2},
+ {name: "above-set", lower: maxValue + 2, upper: maxValue + 2},
+ {name: "overlap", lower: values[0], upper: maxValue},
+ {name: "sparse-gap", lower: values[literalCount/2] + 1, upper: values[literalCount/2] + 1},
Review Comment:
The overlap and sparse-gap cases both land inside the set range, so they go through the slow `removeBoundCheck` and can't show any fast-path gain. Only below-set and above-set do. Worth a note here (or in the PR description) that these two are regression baselines rather than fast-path cases, so the numbers don't get miscredited.
##########
table/in_predicate_extrema_test.go:
##########
@@ -139,6 +140,107 @@ func TestManifestEvaluatorInPredicateExtrema(t *testing.T) {
}
}
+func TestInclusiveMetricsEvaluatorInPredicateExtrema(t *testing.T) {
+ encode := func(value int32) []byte {
+ encoded, err := iceberg.NewLiteral(value).MarshalBinary()
+ require.NoError(t, err)
+
+ return encoded
+ }
+
+ schema := iceberg.NewSchema(1, iceberg.NestedField{ID: 1, Name: "value", Type: iceberg.PrimitiveTypes.Int32})
+ expr := iceberg.IsIn(iceberg.Reference("value"), int32(1), int32(100))
+ eval, err := newInclusiveMetricsEvaluator(schema, expr, true, true)
+ require.NoError(t, err)
+
+ tests := []struct {
+ name string
+ lowerBound []byte
+ upperBound []byte
+ want bool
+ }{
+ {name: "lower bound above set", lowerBound: encode(101), upperBound: encode(200), want: false},
+ {name: "upper bound below set", lowerBound: encode(-10), upperBound: encode(0), want: false},
+ {name: "sparse set has no member in range", lowerBound: encode(40), upperBound: encode(60), want: false},
+ {name: "overlapping range contains member", lowerBound: encode(50), upperBound: encode(100), want: true},
+ {name: "upper bound equals minimum literal", upperBound: encode(1), want: true},
+ {name: "lower bound equals maximum literal", lowerBound: encode(100), want: true},
+ {name: "missing bounds", want: true},
+ {name: "upper bound below set without lower bound", upperBound: encode(0), want: false},
+ {name: "lower bound above set without upper bound", lowerBound: encode(101), want: false},
+ {name: "disjoint lower bound avoids malformed upper bound", lowerBound: encode(101), upperBound: []byte{1}, want: false},
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ file := inclusiveMetricsInTestFile(t, tt.lowerBound, tt.upperBound)
+ got, err := eval(file)
+ require.NoError(t, err)
+ assert.Equal(t, tt.want, got)
+ })
+ }
+
+ t.Run("NaN bounds fail open", func(t *testing.T) {
+ nan, err := iceberg.NewLiteral(math.NaN()).MarshalBinary()
+ require.NoError(t, err)
+ floatSchema := iceberg.NewSchema(1, iceberg.NestedField{
+ ID: 1, Name: "value", Type: iceberg.PrimitiveTypes.Float64,
+ })
+ floatEval, err := newInclusiveMetricsEvaluator(
+ floatSchema, iceberg.IsIn(iceberg.Reference("value"), float64(1), float64(2)), true, true,
+ )
+ require.NoError(t, err)
+
+ got, err := floatEval(inclusiveMetricsInTestFile(t, nan, nan))
+ require.NoError(t, err)
+ assert.True(t, got)
+ })
+
+ t.Run("oversized set keeps existing fallback", func(t *testing.T) {
+ values := make([]int32, inPredicateLimit+1)
+ for i := range values {
+ values[i] = int32(i)
+ }
+ largeEval, err := newInclusiveMetricsEvaluator(
+ schema, iceberg.IsIn(iceberg.Reference("value"), values...), true, true,
+ )
+ require.NoError(t, err)
+
+ got, err := largeEval(inclusiveMetricsInTestFile(
+ t, encode(int32(inPredicateLimit+1)), encode(int32(inPredicateLimit+1)),
Review Comment:
This case is meant to prove the oversized-set fallback fires before the extrema prune, but as written it doesn't isolate that. I'd pick bounds clearly disjoint from the set's range so that if the `Len() > inPredicateLimit` guard regressed, the fast path would prune and flip the expected answer to false. As-is a missing guard could still pass.
##########
table/in_predicate_extrema_bench_test.go:
##########
@@ -116,3 +119,93 @@ func benchmarkManifestIn[T iceberg.LiteralType](b *testing.B, values []T, lower,
manifestInPredicateBenchmarkSink = matched
}
}
+
+func BenchmarkInclusiveMetricsEvalInPredicate(b *testing.B) {
+ for _, literalCount := range []int{10, 50, 200} {
+ values := make([]int32, literalCount)
+ for i := range values {
+ values[i] = int32(i * 2)
+ }
+
+ maxValue := values[len(values)-1]
+ for _, bounds := range []struct {
+ name string
+ lower int32
+ upper int32
+ }{
+ {name: "below-set", lower: -2, upper: -2},
+ {name: "above-set", lower: maxValue + 2, upper: maxValue + 2},
+ {name: "overlap", lower: values[0], upper: maxValue},
+ {name: "sparse-gap", lower: values[literalCount/2] + 1, upper: values[literalCount/2] + 1},
+ } {
+ b.Run("int32/in="+strconv.Itoa(literalCount)+"/"+bounds.name, func(b *testing.B) {
+ benchmarkInclusiveMetricsIn(b, values, bounds.lower, bounds.upper, literalCount, bounds.name == "overlap")
+ })
+ }
+ }
+}
+
+func benchmarkInclusiveMetricsIn(b *testing.B, values []int32, lower, upper int32, literalCount int, wantMatch bool) {
+ b.Helper()
+
+ lowerBytes, err := iceberg.NewLiteral(lower).MarshalBinary()
+ if err != nil {
+ b.Fatal(err)
+ }
+ upperBytes, err := iceberg.NewLiteral(upper).MarshalBinary()
+ if err != nil {
+ b.Fatal(err)
+ }
+
+ schema := iceberg.NewSchema(1, iceberg.NestedField{ID: 1, Name: "value", Type: iceberg.PrimitiveTypes.Int32})
+ eval, err := newInclusiveMetricsEvaluator(
+ schema, iceberg.IsIn(iceberg.Reference("value"), values...), true, true,
+ )
+ if err != nil {
+ b.Fatal(err)
+ }
+
+ builder, err := iceberg.NewDataFileBuilder(
+ *iceberg.UnpartitionedSpec, iceberg.EntryContentData, "file.parquet", iceberg.ParquetFile,
+ nil, nil, nil, 10, 100,
+ )
+ if err != nil {
+ b.Fatal(err)
+ }
+ file := builder.
+ ValueCounts(map[int]int64{1: 10}).
+ NullValueCounts(map[int]int64{1: 0}).
+ NaNValueCounts(map[int]int64{1: 0}).
+ LowerBoundValues(map[int][]byte{1: lowerBytes}).
+ UpperBoundValues(map[int][]byte{1: upperBytes}).
+ Build()
+ files := make([]iceberg.DataFile, 10_000)
+ for i := range files {
+ files[i] = file
+ }
+
+ b.ReportAllocs()
+ b.ReportMetric(float64(len(files)), "files/op")
+ b.ReportMetric(float64(literalCount), "literals/file")
+ b.ResetTimer()
+ for range b.N {
+ matchedFiles := 0
+ for _, file := range files {
Review Comment:
Couple of small things in the bench: the inner `for _, file := range files` shadows the outer `file`, which is legal but confusing, so I'd rename it to `f`. And `wantMatch` is derived from `bounds.name == "overlap"` at the call site; I'd put a `wantMatch bool` field on the bounds case struct instead so the expected result lives with the data.
##########
table/evaluators.go:
##########
@@ -1142,6 +1142,18 @@ func (m *inclusiveMetricsEval) VisitNotEqual(iceberg.BoundTerm, iceberg.Literal)
}
func (m *inclusiveMetricsEval) VisitIn(t iceberg.BoundTerm, s iceberg.Set[iceberg.Literal]) bool {
+ return m.visitIn(t, s, nil, nil)
+}
+
+func (m *inclusiveMetricsEval) VisitInWithExtrema(
Review Comment:
Worth a one-line doc comment spelling out the contract: both `minLit` and `maxLit` must be non-nil (and the actual min/max of `s`), or both nil to get the slow path. Right now a partial-nil call silently falls back, and `manifestEvalVisitor.visitIn` treats the two independently, so the two extrema implementations have different partial-nil semantics. I'd align them or note the difference in the comment.
##########
table/in_predicate_extrema_test.go:
##########
@@ -139,6 +140,107 @@ func TestManifestEvaluatorInPredicateExtrema(t *testing.T) {
}
}
+func TestInclusiveMetricsEvaluatorInPredicateExtrema(t *testing.T) {
+ encode := func(value int32) []byte {
+ encoded, err := iceberg.NewLiteral(value).MarshalBinary()
+ require.NoError(t, err)
+
+ return encoded
+ }
+
+ schema := iceberg.NewSchema(1, iceberg.NestedField{ID: 1, Name: "value", Type: iceberg.PrimitiveTypes.Int32})
+ expr := iceberg.IsIn(iceberg.Reference("value"), int32(1), int32(100))
+ eval, err := newInclusiveMetricsEvaluator(schema, expr, true, true)
+ require.NoError(t, err)
+
+ tests := []struct {
+ name string
+ lowerBound []byte
+ upperBound []byte
+ want bool
+ }{
+ {name: "lower bound above set", lowerBound: encode(101), upperBound: encode(200), want: false},
+ {name: "upper bound below set", lowerBound: encode(-10), upperBound: encode(0), want: false},
+ {name: "sparse set has no member in range", lowerBound: encode(40), upperBound: encode(60), want: false},
+ {name: "overlapping range contains member", lowerBound: encode(50), upperBound: encode(100), want: true},
+ {name: "upper bound equals minimum literal", upperBound: encode(1), want: true},
+ {name: "lower bound equals maximum literal", lowerBound: encode(100), want: true},
+ {name: "missing bounds", want: true},
+ {name: "upper bound below set without lower bound", upperBound: encode(0), want: false},
+ {name: "lower bound above set without upper bound", lowerBound: encode(101), want: false},
+ {name: "disjoint lower bound avoids malformed upper bound", lowerBound: encode(101), upperBound: []byte{1}, want: false},
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ file := inclusiveMetricsInTestFile(t, tt.lowerBound, tt.upperBound)
+ got, err := eval(file)
+ require.NoError(t, err)
+ assert.Equal(t, tt.want, got)
+ })
+ }
+
+ t.Run("NaN bounds fail open", func(t *testing.T) {
Review Comment:
The NaN coverage only hits the both-bounds-NaN case. The `!m.isNan(upperBound)` skip in the extrema branch (a NaN upper with a finite lower) isn't exercised by anything, so I'd add that case plus the mirror finite-upper/NaN-lower so both fail-open branches are pinned.
--
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