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: [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]
