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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
