kumquat-quip opened a new issue, #1479:
URL: https://github.com/apache/arrow-go/issues/1479
### Describe the bug, including details regarding any error messages,
version, and platform.
Building a `Map` array from `ArrayData` (`array.NewMapData`,
`array.MakeFromData`, and so any
`Builder.NewArray()`) takes time exponential in the number of nested map
levels. A single row
of 20 nested maps takes about a second, and 24 levels take 16 s. The same
nesting with `List`
is instant.
There are two causes in `arrow/array/map.go` (v18.8.0, unchanged on `main`).
Each one builds or
visits the map's item subtree twice per level:
```go
func (a *Map) setData(data *Data) {
a.validateData(data)
a.List.setData(data) // a.values =
MakeFromData(entries struct),
// which
already builds keys and items
a.keys = MakeFromData(data.childData[0].Children()[0]) // builds keys
again
a.items = MakeFromData(data.childData[0].Children()[1]) // builds
items again: the whole nested subtree
}
func (a *Map) Retain() {
a.List.Retain() // List.Retain retains a.values (the entries Struct),
and
// Struct.Retain retains its fields: keys and items
a.keys.Retain() // ...and then keys and items are retained again,
a.items.Retain() // recursing into the nested map a second time
}
// Release has the same shape.
```
So construction is O(2^depth), and so is every `Retain`/`Release` of a
nested map (the
builders call these internally too).
Reproduction (one row, one entry per level, `map<utf8, map<utf8, … int64>>`):
```go
package main
import (
"fmt"
"time"
"github.com/apache/arrow-go/v18/arrow"
"github.com/apache/arrow-go/v18/arrow/array"
"github.com/apache/arrow-go/v18/arrow/memory"
)
func build(depth int, wrap func(arrow.DataType) arrow.DataType) arrow.Array {
var dt arrow.DataType = arrow.PrimitiveTypes.Int64
for i := 0; i < depth; i++ {
dt = wrap(dt)
}
b := array.NewBuilder(memory.DefaultAllocator, dt)
defer b.Release()
var appendValue func(array.Builder)
appendValue = func(b array.Builder) {
switch b := b.(type) {
case *array.MapBuilder:
b.Append(true)
b.KeyBuilder().(*array.StringBuilder).Append("k")
appendValue(b.ItemBuilder())
case *array.ListBuilder:
b.Append(true)
appendValue(b.ValueBuilder())
case *array.Int64Builder:
b.Append(1)
}
}
appendValue(b)
return b.NewArray()
}
func main() {
mapOf := func(dt arrow.DataType) arrow.DataType { return
arrow.MapOf(arrow.BinaryTypes.String, dt) }
listOf := func(dt arrow.DataType) arrow.DataType { return
arrow.ListOf(dt) }
for _, depth := range []int{10, 15, 18, 20, 22, 24} {
for _, c := range []struct {
name string
wrap func(arrow.DataType) arrow.DataType
}{{"map", mapOf}, {"list", listOf}} {
start := time.Now()
arr := build(depth, c.wrap)
elapsed := time.Since(start)
arr.Release()
fmt.Printf("depth %2d %-4s %v\n", depth, c.name,
elapsed)
}
}
}
```
Output (arrow-go v18.8.0, Go 1.27.3, Windows 11 amd64):
```
depth 10 map 1.537ms
depth 10 list 0s
depth 15 map 33.2738ms
depth 15 list 0s
depth 18 map 269.1707ms
depth 18 list 0s
depth 20 map 1.0719985s
depth 20 list 0s
depth 22 map 4.2192563s
depth 22 list 0s
depth 24 map 16.2696208s
depth 24 list 0s
```
The time quadruples every two levels. Struct and list nesting stay linear.
We hit this
while adding Trino `MAP` → Arrow map support to the ADBC Trino driver:
deeply nested MAP columns (20+
levels) took seconds per batch to build.
**Suggested fix:** reuse the children that `List.setData` already built, and
let the list's
reference counting cover them, since keys and items are owned by the entries
struct:
```go
func (a *Map) setData(data *Data) {
a.validateData(data)
a.List.setData(data)
entries := a.values.(*Struct)
a.keys = entries.Field(0)
a.items = entries.Field(1)
}
func (a *Map) Retain() { a.List.Retain() }
func (a *Map) Release() { a.List.Release() }
```
With this patch applied locally to v18.8.0, the reproduction is linear
(under 1 ms at every
depth up to 24), and `go test` passes for `./arrow/array/`,
`./arrow/compute/...`,
`./arrow/ipc/...`, `./arrow/cdata/...`, `./arrow/scalar/...` and
`./arrow/avro/...`. A
benchmark with nested maps would catch a regression.
One side effect: `Keys()`/`Items()` become exactly the entries struct's
fields, so they now
honour an offset on the entries struct (as their doc comment already
describes).
### Component(s)
Other (`arrow/array`)
--
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]
