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 bd57a5a6c perf(schema): reuse prefixes when indexing nested field
names (#2270)
bd57a5a6c is described below
commit bd57a5a6ce9416b65decbb023dfab3596712a761
Author: Minh Vu <[email protected]>
AuthorDate: Fri Oct 23 18:32:56 2026 +0200
perf(schema): reuse prefixes when indexing nested field names (#2270)
* perf(schema): reuse path prefixes for nested name indexes
Signed-off-by: Minh Vu <[email protected]>
* test(schema): cover nested name indexing and shorthand aliases
Signed-off-by: Minh Vu <[email protected]>
* test(schema): benchmark wide nested name indexing
Signed-off-by: Minh Vu <[email protected]>
* test(schema): format nested name index cases
Signed-off-by: Minh Vu <[email protected]>
---------
Signed-off-by: Minh Vu <[email protected]>
---
schema.go | 100 +++++++++++++++++---------
schema_name_index_bench_test.go | 90 ++++++++++++++++++++++++
schema_name_index_internal_test.go | 139 +++++++++++++++++++++++++++++++++++++
3 files changed, 298 insertions(+), 31 deletions(-)
diff --git a/schema.go b/schema.go
index e51d1643d..ffbcf1c6c 100644
--- a/schema.go
+++ b/schema.go
@@ -1046,10 +1046,8 @@ func IndexByName(schema *Schema) (map[string]int, error)
{
if len(schema.fields) > 0 {
indexer := &indexByName{
- index: make(map[string]int),
- shortNameId: make(map[string]int),
- fieldNames: make([]string, 0),
- shortFieldNames: make([]string, 0),
+ index: make(map[string]int),
+ shortNameId: make(map[string]int),
}
if _, err := Visit(schema, indexer); err != nil {
return nil, err
@@ -1065,10 +1063,7 @@ func IndexByName(schema *Schema) (map[string]int, error)
{
// a mapping from field ID to field name.
func IndexNameByID(schema *Schema) (map[int]string, error) {
indexer := &indexByName{
- index: make(map[string]int),
- shortNameId: make(map[string]int),
- fieldNames: make([]string, 0),
- shortFieldNames: make([]string, 0),
+ index: make(map[string]int),
}
if _, err := Visit(schema, indexer); err != nil {
return nil, err
@@ -1078,11 +1073,49 @@ func IndexNameByID(schema *Schema) (map[int]string,
error) {
}
type indexByName struct {
- index map[string]int
- shortNameId map[string]int
- combinedIndex map[string]int
- fieldNames []string
- shortFieldNames []string
+ index map[string]int
+ shortNameId map[string]int
+ combinedIndex map[string]int
+
+ fullPath nameIndexPath
+ shortPath nameIndexPath
+}
+
+// nameIndexPath retains a mutable prefix across the schema traversal. Fields
+// at the same level share the prefix instead of repeatedly joining ancestors.
+// Checkpoints also preserve empty path segments, including their separators.
+type nameIndexPath struct {
+ buf []byte
+ checkpoints []int
+}
+
+func (p *nameIndexPath) push(name string) {
+ depth := len(p.checkpoints)
+ p.checkpoints = append(p.checkpoints, len(p.buf))
+ if depth > 0 {
+ p.buf = append(p.buf, '.')
+ }
+ p.buf = append(p.buf, name...)
+}
+
+func (p *nameIndexPath) pop() {
+ last := len(p.checkpoints) - 1
+ p.buf = p.buf[:p.checkpoints[last]]
+ p.checkpoints = p.checkpoints[:last]
+}
+
+func (p *nameIndexPath) prefixedName(name string) string {
+ if len(p.checkpoints) == 0 {
+ return name
+ }
+
+ var b strings.Builder
+ b.Grow(len(p.buf) + 1 + len(name))
+ b.Write(p.buf)
+ b.WriteByte('.')
+ b.WriteString(name)
+
+ return b.String()
}
func (i *indexByName) ByID() map[int]string {
@@ -1104,19 +1137,20 @@ func (i *indexByName) ByName() map[string]int {
func (i *indexByName) Primitive(PrimitiveType) map[string]int { return i.index
}
func (i *indexByName) Variant(VariantType) map[string]int { return i.index
}
func (i *indexByName) addField(name string, fieldID int) {
- fullName := name
- if len(i.fieldNames) > 0 {
- fullName = strings.Join(i.fieldNames, ".") + "." + name
- }
-
+ fullName := i.fullPath.prefixedName(name)
if _, ok := i.index[fullName]; ok {
panic(fmt.Errorf("%w: multiple fields for name %s: %d and %d",
ErrInvalidSchema, fullName, i.index[fullName], fieldID))
}
i.index[fullName] = fieldID
- if len(i.shortFieldNames) > 0 {
- shortName := strings.Join(i.shortFieldNames, ".") + "." + name
+ if len(i.shortPath.checkpoints) > 0 {
+ // A regular struct path is the same in both indexes. Reuse the
+ // immutable full-name string rather than formatting it twice.
+ shortName := fullName
+ if len(i.fullPath.checkpoints) == 0 ||
!bytes.Equal(i.fullPath.buf, i.shortPath.buf) {
+ shortName = i.shortPath.prefixedName(name)
+ }
i.shortNameId[shortName] = fieldID
}
}
@@ -1149,27 +1183,31 @@ func (i *indexByName) Map(mapType MapType, _, _
map[string]int) map[string]int {
}
func (i *indexByName) BeforeListElement(elem NestedField) {
- if _, ok := elem.Type.(*StructType); !ok {
- i.shortFieldNames = append(i.shortFieldNames, elem.Name)
+ if _, ok := elem.Type.(*StructType); !ok && i.shortNameId != nil {
+ i.shortPath.push(elem.Name)
}
- i.fieldNames = append(i.fieldNames, elem.Name)
+ i.fullPath.push(elem.Name)
}
func (i *indexByName) AfterListElement(elem NestedField) {
- if _, ok := elem.Type.(*StructType); !ok {
- i.shortFieldNames = i.shortFieldNames[:len(i.shortFieldNames)-1]
+ if _, ok := elem.Type.(*StructType); !ok && i.shortNameId != nil {
+ i.shortPath.pop()
}
- i.fieldNames = i.fieldNames[:len(i.fieldNames)-1]
+ i.fullPath.pop()
}
func (i *indexByName) BeforeField(field NestedField) {
- i.fieldNames = append(i.fieldNames, field.Name)
- i.shortFieldNames = append(i.shortFieldNames, field.Name)
+ i.fullPath.push(field.Name)
+ if i.shortNameId != nil {
+ i.shortPath.push(field.Name)
+ }
}
-func (i *indexByName) AfterField(field NestedField) {
- i.fieldNames = i.fieldNames[:len(i.fieldNames)-1]
- i.shortFieldNames = i.shortFieldNames[:len(i.shortFieldNames)-1]
+func (i *indexByName) AfterField(NestedField) {
+ i.fullPath.pop()
+ if i.shortNameId != nil {
+ i.shortPath.pop()
+ }
}
// PruneColumns visits a schema pruning any columns which do not exist in the
diff --git a/schema_name_index_bench_test.go b/schema_name_index_bench_test.go
new file mode 100644
index 000000000..b147dc608
--- /dev/null
+++ b/schema_name_index_bench_test.go
@@ -0,0 +1,90 @@
+// 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 (
+ "fmt"
+ "testing"
+)
+
+var (
+ benchmarkNameIndexByName map[string]int
+ benchmarkNameIndexByID map[int]string
+)
+
+func benchmarkWideNestedSchema(width, depth int) *Schema {
+ nextID := 0
+ leaves := make([]NestedField, width)
+ for i := range leaves {
+ nextID++
+ leaves[i] = NestedField{
+ ID: nextID, Name: fmt.Sprintf("column_%d", i), Type:
PrimitiveTypes.Int64,
+ }
+ }
+ for level := range depth {
+ nextID++
+ leaves = []NestedField{{
+ ID: nextID, Name: fmt.Sprintf("nested_%d", level),
+ Type: &StructType{FieldList: leaves},
+ }}
+ }
+
+ return NewSchema(1, leaves...)
+}
+
+func BenchmarkSchemaNameIndexByName(b *testing.B) {
+ for _, tc := range []struct{ width, depth int }{
+ {width: 256, depth: 0},
+ {width: 256, depth: 2},
+ {width: 256, depth: 8},
+ {width: 256, depth: 24},
+ } {
+ b.Run(fmt.Sprintf("width=%d/depth=%d", tc.width, tc.depth),
func(b *testing.B) {
+ schema := benchmarkWideNestedSchema(tc.width, tc.depth)
+ b.ReportAllocs()
+ for range b.N {
+ index, err := IndexByName(schema)
+ if err != nil {
+ b.Fatal(err)
+ }
+ benchmarkNameIndexByName = index
+ }
+ })
+ }
+}
+
+func BenchmarkSchemaNameIndexByID(b *testing.B) {
+ for _, tc := range []struct{ width, depth int }{
+ {width: 256, depth: 0},
+ {width: 256, depth: 2},
+ {width: 256, depth: 8},
+ {width: 256, depth: 24},
+ } {
+ b.Run(fmt.Sprintf("width=%d/depth=%d", tc.width, tc.depth),
func(b *testing.B) {
+ schema := benchmarkWideNestedSchema(tc.width, tc.depth)
+ b.ReportAllocs()
+ for range b.N {
+ index, err := IndexNameByID(schema)
+ if err != nil {
+ b.Fatal(err)
+ }
+ benchmarkNameIndexByID = index
+ }
+ })
+ }
+}
diff --git a/schema_name_index_internal_test.go
b/schema_name_index_internal_test.go
new file mode 100644
index 000000000..df1148813
--- /dev/null
+++ b/schema_name_index_internal_test.go
@@ -0,0 +1,139 @@
+// 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 (
+ "reflect"
+ "strconv"
+ "strings"
+ "testing"
+)
+
+func TestIndexByNameNestedListAliases(t *testing.T) {
+ schema := NewSchema(1,
+ NestedField{ID: 1, Name: "payload", Type:
&StructType{FieldList: []NestedField{
+ {ID: 2, Name: "list", Type: &ListType{
+ ElementID: 3,
+ Element: &StructType{FieldList: []NestedField{
+ {ID: 4, Name: "alpha", Type:
PrimitiveTypes.Int64},
+ {ID: 5, Name: "hidden", Type:
&StructType{FieldList: []NestedField{
+ {ID: 6, Name: "beta", Type:
PrimitiveTypes.String},
+ }}},
+ }},
+ }},
+ }}},
+ NestedField{ID: 7, Name: "sibling", Type:
PrimitiveTypes.String},
+ NestedField{ID: 8, Name: "lookup", Type: &MapType{
+ KeyID: 9, KeyType: PrimitiveTypes.String,
+ ValueID: 10, ValueType: &StructType{FieldList:
[]NestedField{
+ {ID: 11, Name: "東京", Type:
PrimitiveTypes.Int32},
+ }},
+ }},
+ )
+
+ got, err := IndexByName(schema)
+ if err != nil {
+ t.Fatal(err)
+ }
+ want := map[string]int{
+ "payload": 1,
+ "payload.list": 2,
+ "payload.list.element": 3,
+ "payload.list.element.alpha": 4,
+ "payload.list.alpha": 4,
+ "payload.list.element.hidden": 5,
+ "payload.list.hidden": 5,
+ "payload.list.element.hidden.beta": 6,
+ "payload.list.hidden.beta": 6,
+ "sibling": 7,
+ "lookup": 8,
+ "lookup.key": 9,
+ "lookup.value": 10,
+ "lookup.value.東京": 11,
+ }
+ if !reflect.DeepEqual(got, want) {
+ t.Errorf("IndexByName() = %v, want %v", got, want)
+ }
+
+ gotIDs, err := IndexNameByID(schema)
+ if err != nil {
+ t.Fatal(err)
+ }
+ if gotIDs[4] != "payload.list.element.alpha" || gotIDs[6] !=
"payload.list.element.hidden.beta" {
+ t.Errorf("IndexNameByID() lost full list element paths: %v",
gotIDs)
+ }
+ if len(gotIDs) != 11 {
+ t.Errorf("IndexNameByID() has %d entries, want 11", len(gotIDs))
+ }
+}
+
+func TestIndexByNameDeepSiblingRestoration(t *testing.T) {
+ fields := []NestedField{{ID: 1, Name: "leaf", Type:
PrimitiveTypes.Int64}}
+ parts := []string{"leaf"}
+ for depth := range 32 {
+ name := "nested_" + strconv.Itoa(depth)
+ fields = []NestedField{{
+ ID: depth + 2, Name: name, Type: &StructType{FieldList:
fields},
+ }}
+ parts = append([]string{name}, parts...)
+ }
+ fields = append(fields, NestedField{ID: 34, Name: "sibling", Type:
PrimitiveTypes.String})
+ schema := NewSchema(1, fields...)
+
+ byName, err := IndexByName(schema)
+ if err != nil {
+ t.Fatal(err)
+ }
+ if got := byName[strings.Join(parts, ".")]; got != 1 {
+ t.Errorf("deep field ID = %d, want 1", got)
+ }
+ if got := byName["sibling"]; got != 34 {
+ t.Errorf("sibling ID = %d, want 34", got)
+ }
+
+ byID, err := IndexNameByID(schema)
+ if err != nil {
+ t.Fatal(err)
+ }
+ if got := byID[1]; got != strings.Join(parts, ".") {
+ t.Errorf("deep field name = %q, want %q", got,
strings.Join(parts, "."))
+ }
+ if got := byID[34]; got != "sibling" {
+ t.Errorf("sibling name = %q, want sibling", got)
+ }
+}
+
+func TestNameIndexPathEmptySegments(t *testing.T) {
+ var path nameIndexPath
+ path.push("")
+ if got := path.prefixedName("leaf"); got != ".leaf" {
+ t.Errorf("empty prefix: got %q, want .leaf", got)
+ }
+ path.push("inner")
+ if got := path.prefixedName("leaf"); got != ".inner.leaf" {
+ t.Errorf("nested empty prefix: got %q, want .inner.leaf", got)
+ }
+ path.pop()
+ if got := path.prefixedName("other"); got != ".other" {
+ t.Errorf("after pop: got %q, want .other", got)
+ }
+ path.pop()
+ if got := path.prefixedName("top"); got != "top" {
+ t.Errorf("empty stack: got %q, want top", got)
+ }
+}
