This is an automated email from the ASF dual-hosted git repository.
zeroshade pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/iceberg-go.git
The following commit(s) were added to refs/heads/main by this push:
new 6db54d61a feat(table): support sort order satisfaction checks (#2439)
6db54d61a is described below
commit 6db54d61a20ad383a4112373716527abd9977138
Author: Minh Vu <[email protected]>
AuthorDate: Thu Nov 5 21:08:23 2026 +0100
feat(table): support sort order satisfaction checks (#2439)
* feat(table): add Java-compatible sort-order satisfaction checks
* test(table): cover Java sort-order satisfaction rules
* fix(table): avoid conflicting sort transform helper
* fix(table): reject sort satisfaction without source IDs
* test(table): cover source IDs and Java transform edge cases
* style(table): format multi-source sort order test
* test(table): cover full Java time sort satisfaction matrix
* docs(table): clarify limits of Java sort satisfaction
---
table/sort_order_satisfies.go | 112 +++++++++++++++
table/sort_order_satisfies_test.go | 286 +++++++++++++++++++++++++++++++++++++
2 files changed, 398 insertions(+)
diff --git a/table/sort_order_satisfies.go b/table/sort_order_satisfies.go
new file mode 100644
index 000000000..47197e441
--- /dev/null
+++ b/table/sort_order_satisfies.go
@@ -0,0 +1,112 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package table
+
+import (
+ "reflect"
+ "slices"
+
+ "github.com/apache/iceberg-go"
+)
+
+// Satisfies checks whether this sort field satisfies another using Iceberg
+// Java's transform ordering rules. Source IDs, direction, and null ordering
+// must match. This is a metadata compatibility check, not a type-aware proof
+// of physical row ordering (notably for numeric truncation).
+func (s SortField) Satisfies(required SortField) bool {
+ if len(s.SourceIDs) == 0 || !slices.Equal(s.SourceIDs,
required.SourceIDs) ||
+ s.Direction != required.Direction || s.NullOrder !=
required.NullOrder ||
+ isNilSatisfactionTransform(s.Transform) ||
isNilSatisfactionTransform(required.Transform) {
+ return false
+ }
+
+ if s.Transform.Equals(required.Transform) {
+ return true
+ }
+
+ switch transform := s.Transform.(type) {
+ case iceberg.IdentityTransform, *iceberg.IdentityTransform:
+ // Identity preserves the order of every monotonic transform.
+ return required.Transform.PreservesOrder()
+ case iceberg.TruncateTransform:
+ return truncateSatisfies(transform.Width, required.Transform)
+ case *iceberg.TruncateTransform:
+ return truncateSatisfies(transform.Width, required.Transform)
+ }
+
+ actualGranularity := timeSortGranularity(s.Transform)
+ requiredGranularity := timeSortGranularity(required.Transform)
+
+ // A finer time order also satisfies coarser orders: hour > day > month
> year.
+ return actualGranularity != 0 && requiredGranularity != 0 &&
actualGranularity >= requiredGranularity
+}
+
+// Satisfies checks whether this sort order satisfies another using Iceberg
+// Java's field-by-field prefix rules. Order IDs are ignored, and every order
+// satisfies the unsorted order. This is not a proof of physical row ordering:
+// for example, (day(ts), id) satisfies (month(ts), id) by these rules even
+// though IDs need not be globally ordered within each month.
+func (s SortOrder) Satisfies(required SortOrder) bool {
+ if len(s.fields) < len(required.fields) {
+ return false
+ }
+
+ for i, field := range required.fields {
+ if !s.fields[i].Satisfies(field) {
+ return false
+ }
+ }
+
+ return true
+}
+
+func isNilSatisfactionTransform(transform iceberg.Transform) bool {
+ if transform == nil {
+ return true
+ }
+
+ value := reflect.ValueOf(transform)
+
+ return value.Kind() == reflect.Pointer && value.IsNil()
+}
+
+func truncateSatisfies(width int, required iceberg.Transform) bool {
+ switch target := required.(type) {
+ case iceberg.TruncateTransform:
+ return width >= target.Width
+ case *iceberg.TruncateTransform:
+ return target != nil && width >= target.Width
+ default:
+ return false
+ }
+}
+
+func timeSortGranularity(transform iceberg.Transform) int {
+ switch transform.(type) {
+ case iceberg.YearTransform, *iceberg.YearTransform:
+ return 1
+ case iceberg.MonthTransform, *iceberg.MonthTransform:
+ return 2
+ case iceberg.DayTransform, *iceberg.DayTransform:
+ return 3
+ case iceberg.HourTransform, *iceberg.HourTransform:
+ return 4
+ default:
+ return 0
+ }
+}
diff --git a/table/sort_order_satisfies_test.go
b/table/sort_order_satisfies_test.go
new file mode 100644
index 000000000..5cd16d13d
--- /dev/null
+++ b/table/sort_order_satisfies_test.go
@@ -0,0 +1,286 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package table_test
+
+import (
+ "testing"
+
+ "github.com/apache/iceberg-go"
+ "github.com/apache/iceberg-go/table"
+ "github.com/stretchr/testify/require"
+)
+
+func satisfyingSortField(ids []int, transform iceberg.Transform, direction
table.SortDirection, nullOrder table.NullOrder) table.SortField {
+ return table.SortField{
+ SourceIDs: ids,
+ Transform: transform,
+ Direction: direction,
+ NullOrder: nullOrder,
+ }
+}
+
+func satisfyingSortOrder(t *testing.T, id int, fields ...table.SortField)
table.SortOrder {
+ t.Helper()
+
+ order, err := table.NewSortOrder(id, fields)
+ require.NoError(t, err)
+
+ return order
+}
+
+func TestSortOrderSatisfies(t *testing.T) {
+ byID := satisfyingSortField([]int{1}, iceberg.IdentityTransform{},
table.SortASC, table.NullsFirst)
+ byName := satisfyingSortField([]int{2}, iceberg.IdentityTransform{},
table.SortDESC, table.NullsLast)
+ id := satisfyingSortOrder(t, 1, byID)
+ idWithDifferentOrderID := satisfyingSortOrder(t, 99, byID)
+ idAndName := satisfyingSortOrder(t, 2, byID, byName)
+ name := satisfyingSortOrder(t, 3, byName)
+ unsorted := table.UnsortedSortOrder
+
+ cases := []struct {
+ name string
+ actual table.SortOrder
+ required table.SortOrder
+ want bool
+ }{
+ {"unsorted satisfies unsorted", unsorted, unsorted, true},
+ {"any sorted order satisfies unsorted", idAndName, unsorted,
true},
+ {"unsorted does not satisfy sorted", unsorted, id, false},
+ {"an order satisfies itself", idAndName, idAndName, true},
+ {"order IDs do not matter", id, idWithDifferentOrderID, true},
+ {"longer sort satisfies a prefix", idAndName, id, true},
+ {"shorter sort does not satisfy longer", id, idAndName, false},
+ {"non-prefix sort does not satisfy", idAndName, name, false},
+ }
+
+ for _, tc := range cases {
+ t.Run(tc.name, func(t *testing.T) {
+ require.Equal(t, tc.want,
tc.actual.Satisfies(tc.required))
+ })
+ }
+}
+
+func TestSortFieldSatisfiesMatchesSourceDirectionAndNulls(t *testing.T) {
+ base := satisfyingSortField([]int{1, 2}, iceberg.IdentityTransform{},
table.SortDESC, table.NullsLast)
+
+ tests := []struct {
+ name string
+ required table.SortField
+ want bool
+ }{
+ {"same field", base, true},
+ {"different first source", satisfyingSortField([]int{9, 2},
iceberg.IdentityTransform{}, table.SortDESC, table.NullsLast), false},
+ {"different second source", satisfyingSortField([]int{1, 3},
iceberg.IdentityTransform{}, table.SortDESC, table.NullsLast), false},
+ {"missing source", satisfyingSortField([]int{1},
iceberg.IdentityTransform{}, table.SortDESC, table.NullsLast), false},
+ {"reordered sources", satisfyingSortField([]int{2, 1},
iceberg.IdentityTransform{}, table.SortDESC, table.NullsLast), false},
+ {"different direction", satisfyingSortField([]int{1, 2},
iceberg.IdentityTransform{}, table.SortASC, table.NullsLast), false},
+ {"different null order", satisfyingSortField([]int{1, 2},
iceberg.IdentityTransform{}, table.SortDESC, table.NullsFirst), false},
+ }
+
+ for _, tc := range tests {
+ t.Run(tc.name, func(t *testing.T) {
+ require.Equal(t, tc.want, base.Satisfies(tc.required))
+ })
+ }
+}
+
+func TestSortFieldSatisfiesTransformImplications(t *testing.T) {
+ identity := iceberg.IdentityTransform{}
+ truncate2 := iceberg.TruncateTransform{Width: 2}
+ truncate4 := iceberg.TruncateTransform{Width: 4}
+ year := iceberg.YearTransform{}
+ month := iceberg.MonthTransform{}
+ day := iceberg.DayTransform{}
+ hour := iceberg.HourTransform{}
+ bucket4 := iceberg.BucketTransform{NumBuckets: 4}
+ bucket8 := iceberg.BucketTransform{NumBuckets: 8}
+
+ tests := []struct {
+ name string
+ actual iceberg.Transform
+ required iceberg.Transform
+ want bool
+ }{
+ {"identity implies identity", identity, identity, true},
+ {"identity implies truncation", identity, truncate2, true},
+ {"identity implies time transform", identity, hour, true},
+ {"truncation does not imply identity", truncate2, identity,
false},
+ {"wider truncation implies narrower", truncate4, truncate2,
true},
+ {"narrower truncation does not imply wider", truncate2,
truncate4, false},
+ {"truncation implies itself", truncate4, truncate4, true},
+ {"time transform does not imply truncation", day, truncate2,
false},
+ {"truncation does not imply time transform", truncate4, year,
false},
+ {"hour implies day", hour, day, true},
+ {"hour implies month", hour, month, true},
+ {"hour implies year", hour, year, true},
+ {"day implies month", day, month, true},
+ {"day implies year", day, year, true},
+ {"month implies year", month, year, true},
+ {"month does not imply day", month, day, false},
+ {"year does not imply month", year, month, false},
+ {"day does not imply hour", day, hour, false},
+ {"same bucket transform", bucket4, bucket4, true},
+ {"different bucket transforms", bucket4, bucket8, false},
+ {"identity does not imply bucket", identity, bucket4, false},
+ {"pointer truncate transform", &truncate4, &truncate2, true},
+ {"pointer time transform", &hour, &year, true},
+ }
+
+ for _, tc := range tests {
+ t.Run(tc.name, func(t *testing.T) {
+ actual := satisfyingSortField([]int{7}, tc.actual,
table.SortASC, table.NullsLast)
+ required := satisfyingSortField([]int{7}, tc.required,
table.SortASC, table.NullsLast)
+ require.Equal(t, tc.want, actual.Satisfies(required))
+ })
+ }
+}
+
+func TestSortOrderSatisfiesTransformOnPrefixOnly(t *testing.T) {
+ year := satisfyingSortField([]int{1}, iceberg.YearTransform{},
table.SortASC, table.NullsLast)
+ day := satisfyingSortField([]int{1}, iceberg.DayTransform{},
table.SortASC, table.NullsLast)
+ byName := satisfyingSortField([]int{2}, iceberg.IdentityTransform{},
table.SortDESC, table.NullsLast)
+
+ actual := satisfyingSortOrder(t, 1, day, byName)
+ required := satisfyingSortOrder(t, 2, year)
+ require.True(t, actual.Satisfies(required))
+ require.False(t, required.Satisfies(actual))
+
+ wrongSuffix := satisfyingSortOrder(t, 3, year,
satisfyingSortField([]int{2}, iceberg.IdentityTransform{}, table.SortASC,
table.NullsLast))
+ require.False(t, actual.Satisfies(wrongSuffix))
+}
+
+func TestSortFieldSatisfiesRejectsNilTransforms(t *testing.T) {
+ valid := satisfyingSortField([]int{1}, iceberg.IdentityTransform{},
table.SortASC, table.NullsFirst)
+ missing := satisfyingSortField([]int{1}, nil, table.SortASC,
table.NullsFirst)
+ require.False(t, valid.Satisfies(missing))
+ require.False(t, missing.Satisfies(valid))
+
+ var nilTruncate *iceberg.TruncateTransform
+ typedNil := satisfyingSortField([]int{1}, nilTruncate, table.SortASC,
table.NullsFirst)
+ require.False(t, typedNil.Satisfies(valid))
+ require.False(t, valid.Satisfies(typedNil))
+}
+
+func TestSortFieldSatisfiesRequiresSourceIDs(t *testing.T) {
+ valid := satisfyingSortField([]int{1}, iceberg.IdentityTransform{},
table.SortASC, table.NullsLast)
+ noSources := satisfyingSortField(nil, iceberg.IdentityTransform{},
table.SortASC, table.NullsLast)
+ emptySources := satisfyingSortField([]int{},
iceberg.IdentityTransform{}, table.SortASC, table.NullsLast)
+
+ require.False(t, noSources.Satisfies(noSources))
+ require.False(t, noSources.Satisfies(emptySources))
+ require.False(t, valid.Satisfies(noSources))
+ require.False(t, noSources.Satisfies(valid))
+}
+
+func TestSortFieldSatisfiesOpaqueTransforms(t *testing.T) {
+ unknown, err := iceberg.ParseTransform("custom-sort[4]")
+ require.NoError(t, err)
+ sameUnknown, err := iceberg.ParseTransform("custom-sort[4]")
+ require.NoError(t, err)
+ otherUnknown, err := iceberg.ParseTransform("custom-sort[8]")
+ require.NoError(t, err)
+
+ field := func(transform iceberg.Transform) table.SortField {
+ return satisfyingSortField([]int{1}, transform, table.SortASC,
table.NullsLast)
+ }
+
+ require.True(t, field(unknown).Satisfies(field(sameUnknown)))
+ require.False(t, field(unknown).Satisfies(field(otherUnknown)))
+ require.False(t,
field(iceberg.IdentityTransform{}).Satisfies(field(unknown)))
+ require.False(t,
field(unknown).Satisfies(field(iceberg.IdentityTransform{})))
+ require.True(t,
field(iceberg.VoidTransform{}).Satisfies(field(iceberg.VoidTransform{})))
+ require.False(t,
field(iceberg.VoidTransform{}).Satisfies(field(iceberg.IdentityTransform{})))
+}
+
+func TestSortFieldSatisfiesMixedPointerAndValueTransforms(t *testing.T) {
+ identity := iceberg.IdentityTransform{}
+ year := iceberg.YearTransform{}
+ day := iceberg.DayTransform{}
+ truncate2 := iceberg.TruncateTransform{Width: 2}
+ truncate4 := iceberg.TruncateTransform{Width: 4}
+ bucket := iceberg.BucketTransform{NumBuckets: 4}
+
+ field := func(transform iceberg.Transform) table.SortField {
+ return satisfyingSortField([]int{1}, transform, table.SortDESC,
table.NullsFirst)
+ }
+
+ require.True(t, field(&identity).Satisfies(field(identity)))
+ require.True(t, field(identity).Satisfies(field(&identity)))
+ require.True(t, field(&identity).Satisfies(field(&year)))
+ require.True(t, field(&day).Satisfies(field(year)))
+ require.True(t, field(day).Satisfies(field(&year)))
+ require.False(t, field(&year).Satisfies(field(day)))
+ require.True(t, field(&truncate4).Satisfies(field(truncate2)))
+ require.True(t, field(truncate4).Satisfies(field(&truncate2)))
+ require.False(t, field(&truncate2).Satisfies(field(&truncate4)))
+ require.True(t, field(&bucket).Satisfies(field(bucket)))
+ require.True(t, field(bucket).Satisfies(field(&bucket)))
+}
+
+func TestSortOrderSatisfiesMultiSourceField(t *testing.T) {
+ transform, err := iceberg.ParseTransform("multi-source[2]")
+ require.NoError(t, err)
+
+ field := func(ids []int) table.SortField {
+ return satisfyingSortField(ids, transform, table.SortASC,
table.NullsLast)
+ }
+
+ actual := satisfyingSortOrder(t, 1,
+ field([]int{1, 2}),
+ satisfyingSortField([]int{3}, iceberg.IdentityTransform{},
table.SortASC, table.NullsLast),
+ )
+ compatible := satisfyingSortOrder(t, 2, field([]int{1, 2}))
+ reversed := satisfyingSortOrder(t, 3, field([]int{2, 1}))
+ shorterSourceList := satisfyingSortOrder(t, 4, field([]int{1}))
+
+ require.True(t, actual.Satisfies(compatible))
+ require.False(t, compatible.Satisfies(actual))
+ require.False(t, actual.Satisfies(reversed))
+ require.False(t, actual.Satisfies(shorterSourceList))
+}
+
+func TestSortFieldSatisfiesRejectsTwoTypedNilTransforms(t *testing.T) {
+ var nilTruncate *iceberg.TruncateTransform
+ field := satisfyingSortField([]int{1}, nilTruncate, table.SortASC,
table.NullsFirst)
+
+ require.False(t, field.Satisfies(field))
+}
+
+func TestSortFieldSatisfiesCompleteTimeTransformMatrix(t *testing.T) {
+ // Mirror Java TestTimeTransforms for all 16 relationships.
+ // The ordering implications apply equally to descending sorts.
+ transforms := []struct {
+ name string
+ transform iceberg.Transform
+ }{
+ {"year", iceberg.YearTransform{}},
+ {"month", iceberg.MonthTransform{}},
+ {"day", iceberg.DayTransform{}},
+ {"hour", iceberg.HourTransform{}},
+ }
+
+ for actualIndex, actual := range transforms {
+ for requiredIndex, required := range transforms {
+ t.Run(actual.name+"-to-"+required.name, func(t
*testing.T) {
+ actualField := satisfyingSortField([]int{1},
actual.transform, table.SortDESC, table.NullsLast)
+ requiredField := satisfyingSortField([]int{1},
required.transform, table.SortDESC, table.NullsLast)
+ require.Equal(t, actualIndex >= requiredIndex,
actualField.Satisfies(requiredField))
+ })
+ }
+ }
+}
