Skip to content

Commit 9b4c972

Browse files
zeroshadezagtopitrouwestonpace
authored
GH-32949: [Go] REE Array IPC read/write (#14223)
* Closes: #32949 Lead-authored-by: Matt Topol <[email protected]> Co-authored-by: zagto <[email protected]> Co-authored-by: Antoine Pitrou <[email protected]> Co-authored-by: Weston Pace <[email protected]> Signed-off-by: Matt Topol <[email protected]>
1 parent 9e7b79b commit 9b4c972

17 files changed

Lines changed: 1025 additions & 37 deletions

File tree

‎dev/archery/archery/integration/datagen.py‎

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -193,6 +193,35 @@ def generate_range(self, size, lower, upper, name=None,
193193
return PrimitiveColumn(name, size, is_valid, values)
194194

195195

196+
# Integer field that fulfils the requirements for the run ends field of REE.
197+
# The integers are positive and in a strictly increasing sequence
198+
class RunEndsField(IntegerField):
199+
# bit_width should only be one of 16/32/64
200+
def __init__(self, name, bit_width, *, metadata=None):
201+
super().__init__(name, is_signed=True, bit_width=bit_width,
202+
nullable=False, metadata=metadata, min_value=1)
203+
204+
def generate_range(self, size, lower, upper, name=None,
205+
include_extremes=False):
206+
rng = np.random.default_rng()
207+
# generate values that are strictly increasing with a min-value of
208+
# 1, but don't go higher than the max signed value for the given
209+
# bit width. We sort the values to ensure they are strictly increasing
210+
# and set replace to False to avoid duplicates, ensuring a valid
211+
# run-ends array.
212+
values = rng.choice(2 ** (self.bit_width - 1) - 1, size=size, replace=False)
213+
values += 1
214+
values = sorted(values)
215+
values = list(map(int if self.bit_width < 64 else str, values))
216+
# RunEnds cannot be null, as such self.nullable == False and this
217+
# will generate a validity map of all ones.
218+
is_valid = self._make_is_valid(size)
219+
220+
if name is None:
221+
name = self.name
222+
return PrimitiveColumn(name, size, is_valid, values)
223+
224+
196225
class DateField(IntegerField):
197226

198227
DAY = 0
@@ -939,6 +968,33 @@ def generate_column(self, size, name=None):
939968
return StructColumn(name, size, is_valid, field_values)
940969

941970

971+
class RunEndEncodedField(Field):
972+
973+
def __init__(self, name, run_ends_bitwidth, values_field, *, nullable=True,
974+
metadata=None):
975+
super().__init__(name, nullable=nullable, metadata=metadata)
976+
self.run_ends_field = RunEndsField('run_ends', run_ends_bitwidth)
977+
self.values_field = values_field
978+
979+
def _get_type(self):
980+
return OrderedDict([
981+
('name', 'runendencoded')
982+
])
983+
984+
def _get_children(self):
985+
return [
986+
self.run_ends_field.get_json(),
987+
self.values_field.get_json()
988+
]
989+
990+
def generate_column(self, size, name=None):
991+
values = self.values_field.generate_column(size)
992+
run_ends = self.run_ends_field.generate_column(size)
993+
if name is None:
994+
name = self.name
995+
return RunEndEncodedColumn(name, size, run_ends, values)
996+
997+
942998
class _BaseUnionField(Field):
943999

9441000
def __init__(self, name, fields, type_ids=None, *, nullable=True,
@@ -1104,6 +1160,20 @@ def _get_children(self):
11041160
return [field.get_json() for field in self.field_values]
11051161

11061162

1163+
class RunEndEncodedColumn(Column):
1164+
1165+
def __init__(self, name, count, run_ends_field, values_field):
1166+
super().__init__(name, count)
1167+
self.run_ends = run_ends_field
1168+
self.values = values_field
1169+
1170+
def _get_buffers(self):
1171+
return []
1172+
1173+
def _get_children(self):
1174+
return [self.run_ends.get_json(), self.values.get_json()]
1175+
1176+
11071177
class SparseUnionColumn(Column):
11081178

11091179
def __init__(self, name, count, type_ids, field_values):
@@ -1461,6 +1531,16 @@ def generate_recursive_nested_case():
14611531
return _generate_file("recursive_nested", fields, batch_sizes)
14621532

14631533

1534+
def generate_run_end_encoded_case():
1535+
fields = [
1536+
RunEndEncodedField('ree16', 16, get_field('values', 'int32')),
1537+
RunEndEncodedField('ree32', 32, get_field('values', 'utf8')),
1538+
RunEndEncodedField('ree64', 64, get_field('values', 'float32')),
1539+
]
1540+
batch_sizes = [0, 7, 10]
1541+
return _generate_file("run_end_encoded", fields, batch_sizes)
1542+
1543+
14641544
def generate_nested_large_offsets_case():
14651545
fields = [
14661546
LargeListField('large_list_nullable', get_field('item', 'int32')),
@@ -1659,6 +1739,13 @@ def _temp_path():
16591739
.skip_category('Java') # TODO(ARROW-7779)
16601740
.skip_category('JS'),
16611741

1742+
generate_run_end_encoded_case()
1743+
.skip_category('C++')
1744+
.skip_category('C#')
1745+
.skip_category('Java')
1746+
.skip_category('JS')
1747+
.skip_category('Rust'),
1748+
16621749
generate_extension_case()
16631750
.skip_category('C#')
16641751
.skip_category('JS'),

‎docs/source/format/Integration.rst‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -309,6 +309,17 @@ Null: ::
309309
"name": "null"
310310
}
311311

312+
RunEndEncoded: ::
313+
314+
{
315+
"name": "runendencoded"
316+
}
317+
318+
The ``Field``'s "children" should be exactly two child fields. The first
319+
child must be named "run_ends", be non-nullable and be either an ``int16``,
320+
``int32``, or ``int64`` type field. The second child must be named "values",
321+
but can be of any type.
322+
312323
Extension types are, as in the IPC format, represented as their underlying
313324
storage type plus some dedicated field metadata to reconstruct the extension
314325
type. For example, assuming a "uuid" extension type backed by a

‎docs/source/status.rst‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -96,6 +96,8 @@ Data Types
9696
+-------------------+-------+-------+-------+------------+-------+-------+-------+
9797
| Extension | ✓ | ✓ | ✓ | | | ✓ | ✓ |
9898
+-------------------+-------+-------+-------+------------+-------+-------+-------+
99+
| Run-End Encoded | | | ✓ | | | | |
100+
+-------------------+-------+-------+-------+------------+-------+-------+-------+
99101

100102
Notes:
101103

‎go/arrow/array/encoded.go‎

Lines changed: 149 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -20,12 +20,14 @@ import (
2020
"bytes"
2121
"fmt"
2222
"math"
23+
"reflect"
2324
"sync/atomic"
2425

2526
"github.com/apache/arrow/go/v12/arrow"
2627
"github.com/apache/arrow/go/v12/arrow/encoded"
2728
"github.com/apache/arrow/go/v12/arrow/internal/debug"
2829
"github.com/apache/arrow/go/v12/arrow/memory"
30+
"github.com/apache/arrow/go/v12/internal/utils"
2931
"github.com/goccy/go-json"
3032
)
3133

@@ -68,6 +70,102 @@ func (r *RunEndEncoded) Release() {
6870
r.ends.Release()
6971
}
7072

73+
// LogicalValuesArray returns an array holding the values of each
74+
// run, only over the range of run values inside the logical offset/length
75+
// range of the parent array.
76+
//
77+
// Example
78+
//
79+
// For this array:
80+
// RunEndEncoded: { Offset: 150, Length: 1500 }
81+
// RunEnds: [ 1, 2, 4, 6, 10, 1000, 1750, 2000 ]
82+
// Values: [ "a", "b", "c", "d", "e", "f", "g", "h" ]
83+
//
84+
// LogicalValuesArray will return the following array:
85+
// [ "f", "g" ]
86+
//
87+
// This is because the offset of 150 tells it to skip the values until
88+
// "f" which corresponds with the logical offset (the run from 10 - 1000),
89+
// and stops after "g" because the length + offset goes to 1650 which is
90+
// within the run from 1000 - 1750, corresponding to the "g" value.
91+
//
92+
// Note
93+
//
94+
// The return from this needs to be Released.
95+
func (r *RunEndEncoded) LogicalValuesArray() arrow.Array {
96+
physOffset := r.GetPhysicalOffset()
97+
physLength := r.GetPhysicalLength()
98+
data := NewSliceData(r.data.Children()[1], int64(physOffset), int64(physOffset+physLength))
99+
defer data.Release()
100+
return MakeFromData(data)
101+
}
102+
103+
// LogicalRunEndsArray returns an array holding the logical indexes
104+
// of each run end, only over the range of run end values relative
105+
// to the logical offset/length range of the parent array.
106+
//
107+
// For arrays with an offset, this is not a slice of the existing
108+
// internal run ends array. Instead a new array is created with run-ends
109+
// that are adjusted so the new array can have an offset of 0. As a result
110+
// this method can be expensive to call for an array with a non-zero offset.
111+
//
112+
// Example
113+
//
114+
// For this array:
115+
// RunEndEncoded: { Offset: 150, Length: 1500 }
116+
// RunEnds: [ 1, 2, 4, 6, 10, 1000, 1750, 2000 ]
117+
// Values: [ "a", "b", "c", "d", "e", "f", "g", "h" ]
118+
//
119+
// LogicalRunEndsArray will return the following array:
120+
// [ 850, 1500 ]
121+
//
122+
// This is because the offset of 150 tells us to skip all run-ends less
123+
// than 150 (by finding the physical offset), and we adjust the run-ends
124+
// accordingly (1000 - 150 = 850). The logical length of the array is 1500,
125+
// so we know we don't want to go past the 1750 run end. Thus the last
126+
// run-end is determined by doing: min(1750 - 150, 1500) = 1500.
127+
//
128+
// Note
129+
//
130+
// The return from this needs to be Released
131+
func (r *RunEndEncoded) LogicalRunEndsArray(mem memory.Allocator) arrow.Array {
132+
physOffset := r.GetPhysicalOffset()
133+
physLength := r.GetPhysicalLength()
134+
135+
if r.data.offset == 0 {
136+
data := NewSliceData(r.data.childData[0], 0, int64(physLength))
137+
defer data.Release()
138+
return MakeFromData(data)
139+
}
140+
141+
bldr := NewBuilder(mem, r.data.childData[0].DataType())
142+
defer bldr.Release()
143+
bldr.Resize(physLength)
144+
145+
switch e := r.ends.(type) {
146+
case *Int16:
147+
for _, v := range e.Int16Values()[physOffset : physOffset+physLength] {
148+
v -= int16(r.data.offset)
149+
v = int16(utils.MinInt(int(v), r.data.length))
150+
bldr.(*Int16Builder).Append(v)
151+
}
152+
case *Int32:
153+
for _, v := range e.Int32Values()[physOffset : physOffset+physLength] {
154+
v -= int32(r.data.offset)
155+
v = int32(utils.MinInt(int(v), r.data.length))
156+
bldr.(*Int32Builder).Append(v)
157+
}
158+
case *Int64:
159+
for _, v := range e.Int64Values()[physOffset : physOffset+physLength] {
160+
v -= int64(r.data.offset)
161+
v = int64(utils.MinInt(int(v), r.data.length))
162+
bldr.(*Int64Builder).Append(v)
163+
}
164+
}
165+
166+
return bldr.NewArray()
167+
}
168+
71169
func (r *RunEndEncoded) setData(data *Data) {
72170
if len(data.childData) != 2 {
73171
panic(fmt.Errorf("%w: arrow/array: RLE array must have exactly 2 children", arrow.ErrInvalid))
@@ -101,25 +199,30 @@ func (r *RunEndEncoded) String() string {
101199
if i != 0 {
102200
buf.WriteByte(',')
103201
}
104-
fmt.Fprintf(&buf, "{%v -> %v}",
202+
203+
value := r.values.(arraymarshal).getOneForMarshal(i)
204+
if byts, ok := value.(json.RawMessage); ok {
205+
value = string(byts)
206+
}
207+
fmt.Fprintf(&buf, "{%d -> %v}",
105208
r.ends.(arraymarshal).getOneForMarshal(i),
106-
r.values.(arraymarshal).getOneForMarshal(i))
209+
value)
107210
}
108211

109212
buf.WriteByte(']')
110213
return buf.String()
111214
}
112215

113216
func (r *RunEndEncoded) getOneForMarshal(i int) interface{} {
114-
return [2]interface{}{r.ends.(arraymarshal).getOneForMarshal(i),
115-
r.values.(arraymarshal).getOneForMarshal(i)}
217+
physIndex := encoded.FindPhysicalIndex(r.data, i+r.data.offset)
218+
return r.values.(arraymarshal).getOneForMarshal(physIndex)
116219
}
117220

118221
func (r *RunEndEncoded) MarshalJSON() ([]byte, error) {
119222
var buf bytes.Buffer
120223
enc := json.NewEncoder(&buf)
121224
buf.WriteByte('[')
122-
for i := 0; i < r.ends.Len(); i++ {
225+
for i := 0; i < r.Len(); i++ {
123226
if i != 0 {
124227
buf.WriteByte(',')
125228
}
@@ -166,6 +269,8 @@ type RunEndEncodedBuilder struct {
166269
runEnds Builder
167270
values Builder
168271
maxRunEnd uint64
272+
273+
lastUnmarshalled interface{}
169274
}
170275

171276
func NewRunEndEncodedBuilder(mem memory.Allocator, runEnds, encoded arrow.DataType) *RunEndEncodedBuilder {
@@ -184,11 +289,12 @@ func NewRunEndEncodedBuilder(mem memory.Allocator, runEnds, encoded arrow.DataTy
184289
maxEnd = math.MaxInt64
185290
}
186291
return &RunEndEncodedBuilder{
187-
builder: builder{refCount: 1, mem: mem},
188-
dt: dt,
189-
runEnds: NewBuilder(mem, runEnds),
190-
values: NewBuilder(mem, encoded),
191-
maxRunEnd: maxEnd,
292+
builder: builder{refCount: 1, mem: mem},
293+
dt: dt,
294+
runEnds: NewBuilder(mem, runEnds),
295+
values: NewBuilder(mem, encoded),
296+
maxRunEnd: maxEnd,
297+
lastUnmarshalled: nil,
192298
}
193299
}
194300

@@ -214,6 +320,7 @@ func (b *RunEndEncodedBuilder) addLength(n uint64) {
214320
}
215321

216322
func (b *RunEndEncodedBuilder) finishRun() {
323+
b.lastUnmarshalled = nil
217324
if b.length == 0 {
218325
return
219326
}
@@ -233,6 +340,12 @@ func (b *RunEndEncodedBuilder) Append(n uint64) {
233340
b.finishRun()
234341
b.addLength(n)
235342
}
343+
func (b *RunEndEncodedBuilder) AppendRuns(runs []uint64) {
344+
for _, r := range runs {
345+
b.finishRun()
346+
b.addLength(r)
347+
}
348+
}
236349
func (b *RunEndEncodedBuilder) ContinueRun(n uint64) {
237350
b.addLength(n)
238351
}
@@ -285,10 +398,35 @@ func (b *RunEndEncodedBuilder) newData() (data *Data) {
285398
}
286399

287400
func (b *RunEndEncodedBuilder) unmarshalOne(dec *json.Decoder) error {
288-
return arrow.ErrNotImplemented
401+
var value interface{}
402+
if err := dec.Decode(&value); err != nil {
403+
return err
404+
}
405+
406+
// if we unmarshalled the same value as the previous one, we want to
407+
// continue the run. However, there's an edge case. At the start of
408+
// unmarshalling, lastUnmarshalled will be nil, but we might get
409+
// nil as the first value we unmarshal. In that case we want to
410+
// make sure we add a new run instead. We can detect that case by
411+
// checking that the number of runEnds matches the number of values
412+
// we have, which means no matter what we have to start a new run
413+
if reflect.DeepEqual(value, b.lastUnmarshalled) && (value != nil || b.runEnds.Len() != b.values.Len()) {
414+
b.ContinueRun(1)
415+
return nil
416+
}
417+
418+
data, err := json.Marshal(value)
419+
if err != nil {
420+
return err
421+
}
422+
423+
b.Append(1)
424+
b.lastUnmarshalled = value
425+
return b.ValueBuilder().unmarshalOne(json.NewDecoder(bytes.NewReader(data)))
289426
}
290427

291428
func (b *RunEndEncodedBuilder) unmarshal(dec *json.Decoder) error {
429+
b.finishRun()
292430
for dec.More() {
293431
if err := b.unmarshalOne(dec); err != nil {
294432
return err

0 commit comments

Comments
 (0)