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