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/arrow-go.git
The following commit(s) were added to refs/heads/main by this push:
new a1416188 perf(arrow/array): compare binary values by valid runs (#1174)
a1416188 is described below
commit a1416188efb6bfc4cd3609f28d3e312b9eef8eda
Author: Minh Vu <[email protected]>
AuthorDate: Wed Sep 2 19:42:50 2026 +0200
perf(arrow/array): compare binary values by valid runs (#1174)
### Rationale for this change
Binary and string equality currently compares every non-null value
separately. This repeats offset lookups and small byte or string
comparisons even when a long valid run is stored contiguously.
### What changes are included in this PR?
- Walk contiguous valid runs for Binary, String, LargeBinary, and
LargeString.
- Compare each run payload in one operation.
- Verify every value length so equal concatenated bytes with different
boundaries still compare unequal.
- Keep null payloads ignored.
- Sample validity fragmentation and retain the scalar path for many tiny
runs.
- Add benchmarks and tests for offsets, null patterns, mismatches, and
value boundaries.
Apple M1 Pro results for 65,536 values of 32 bytes with `-cpu=1`:
| Case | Before | After | Speedup |
| --- | ---: | ---: | ---: |
| Binary equal | 644 us | 360 us | 1.79x |
| Binary 10% null | 582 us | 439 us | 1.33x |
| Binary mismatch last | 648 us | 350 us | 1.85x |
| Binary different length | 453 us | 262 us | 1.73x |
| String equal | 633 us | 390 us | 1.62x |
| String 10% null | 604 us | 496 us | 1.22x |
| String mismatch last | 664 us | 406 us | 1.64x |
| String different length | 426 us | 235 us | 1.81x |
The alternating 50% null case selects the scalar path and remains
neutral. All benchmark cases stay at zero allocations.
### Are these changes tested?
Yes.
- `go test ./arrow/...`
- `go test -race ./arrow/array`
- `go vet -composites=false ./arrow/array`
- Cross-compiled array tests for linux/amd64 and linux/s390x.
### Are there any user-facing changes?
No.
---
arrow/array/binary.go | 140 +++++++-
arrow/array/binary_equality_benchmark_test.go | 131 ++++++++
arrow/array/binary_equality_test.go | 444 ++++++++++++++++++++++++++
arrow/array/string.go | 44 ++-
4 files changed, 734 insertions(+), 25 deletions(-)
diff --git a/arrow/array/binary.go b/arrow/array/binary.go
index fe986583..c2fde2af 100644
--- a/arrow/array/binary.go
+++ b/arrow/array/binary.go
@@ -24,7 +24,9 @@ import (
"unsafe"
"github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/bitutil"
"github.com/apache/arrow-go/v18/arrow/memory"
+ "github.com/apache/arrow-go/v18/internal/bitutils"
"github.com/apache/arrow-go/v18/internal/json"
)
@@ -231,15 +233,21 @@ func (a *Binary) ValidateFull() error {
}
func arrayEqualBinary(left, right *Binary) bool {
- for i := 0; i < left.Len(); i++ {
- if left.IsNull(i) {
- continue
- }
- if !bytes.Equal(left.Value(i), right.Value(i)) {
- return false
+ if useScalarVariableWidthEquality(left) {
+ for i := range left.Len() {
+ if !left.IsNull(i) && !bytes.Equal(left.Value(i),
right.Value(i)) {
+ return false
+ }
}
+ return true
}
- return true
+ return arrayEqualVariableWidth(
+ left.valueOffsets, right.valueOffsets,
+ left.valueBytes, right.valueBytes,
+ left.Offset(), right.Offset(), left.Len(),
+ left.NullN(), left.NullBitmapBytes(),
+ bytes.Equal,
+ )
}
type LargeBinary struct {
@@ -432,17 +440,127 @@ func (a *LargeBinary) ValidateFull() error {
}
func arrayEqualLargeBinary(left, right *LargeBinary) bool {
- for i := 0; i < left.Len(); i++ {
- if left.IsNull(i) {
- continue
+ if useScalarVariableWidthEquality(left) {
+ for i := range left.Len() {
+ if !left.IsNull(i) && !bytes.Equal(left.Value(i),
right.Value(i)) {
+ return false
+ }
+ }
+ return true
+ }
+ return arrayEqualVariableWidth(
+ left.valueOffsets, right.valueOffsets,
+ left.valueBytes, right.valueBytes,
+ left.Offset(), right.Offset(), left.Len(),
+ left.NullN(), left.NullBitmapBytes(),
+ bytes.Equal,
+ )
+}
+
+type binaryOffset interface {
+ ~int32 | ~int64
+}
+
+func useScalarVariableWidthEquality(values arrow.Array) bool {
+ if values.NullN() == 0 {
+ return false
+ }
+ if values.Len() <= 64 || len(values.NullBitmapBytes()) == 0 {
+ return true
+ }
+
+ // Very short validity runs cost more to set up than direct value
comparisons.
+ // Sample a few runs and retain the scalar path when they average under
four values.
+ const (
+ sampleRuns = 8
+ minAverageRunLength = 4
+ )
+ runs := bitutils.NewSetBitRunReader(
+ values.NullBitmapBytes(), int64(values.Data().Offset()),
int64(values.Len()),
+ )
+ validValues := int64(0)
+ for range sampleRuns {
+ run := runs.NextRun()
+ if run.Length == 0 {
+ return false
+ }
+ validValues += run.Length
+ }
+ return validValues < sampleRuns*minAverageRunLength
+}
+
+func arrayEqualVariableWidth[T binaryOffset, V ~[]byte | ~string](
+ leftOffsets, rightOffsets []T,
+ leftValues, rightValues V,
+ leftOffset, rightOffset, length, nulls int,
+ validity []byte,
+ equalValues func(V, V) bool,
+) bool {
+ if length == 0 {
+ return true
+ }
+
+ // A declared null count may be inconsistent with the validity bitmap.
+ // Verify zero-null bitmaps before comparing the whole payload.
+ if len(validity) == 0 ||
+ (nulls == 0 && bitutil.CountSetBits(validity, leftOffset,
length) == length) {
+ return arrayEqualVariableWidthRun(
+ leftOffsets, rightOffsets,
+ leftValues, rightValues,
+ leftOffset, rightOffset, length,
+ equalValues,
+ )
+ }
+
+ runs := bitutils.NewSetBitRunReader(validity, int64(leftOffset),
int64(length))
+ for {
+ run := runs.NextRun()
+ if run.Length == 0 {
+ return true
+ }
+ if !arrayEqualVariableWidthRun(
+ leftOffsets, rightOffsets,
+ leftValues, rightValues,
+ leftOffset+int(run.Pos), rightOffset+int(run.Pos),
int(run.Length),
+ equalValues,
+ ) {
+ return false
}
- if !bytes.Equal(left.Value(i), right.Value(i)) {
+ }
+}
+
+func arrayEqualVariableWidthRun[T binaryOffset, V ~[]byte | ~string](
+ leftOffsets, rightOffsets []T,
+ leftValues, rightValues V,
+ leftOffset, rightOffset, length int,
+ equalValues func(V, V) bool,
+) bool {
+ leftStart, leftEnd := leftOffsets[leftOffset],
leftOffsets[leftOffset+length]
+ rightStart, rightEnd := rightOffsets[rightOffset],
rightOffsets[rightOffset+length]
+ if leftEnd-leftStart != rightEnd-rightStart ||
+ !equalValues(
+ sliceBinaryValues(leftValues, leftStart, leftEnd),
+ sliceBinaryValues(rightValues, rightStart, rightEnd),
+ ) {
+ return false
+ }
+ if length == 1 {
+ return true
+ }
+
+ for i := range length {
+ if leftOffsets[leftOffset+i+1]-leftOffsets[leftOffset+i] !=
+
rightOffsets[rightOffset+i+1]-rightOffsets[rightOffset+i] {
return false
}
}
return true
}
+func sliceBinaryValues[T binaryOffset, V ~[]byte | ~string](values V, start,
end T) V {
+ return values[start:end]
+}
+
type ViewLike interface {
arrow.Array
ValueHeader(int) *arrow.ViewHeader
diff --git a/arrow/array/binary_equality_benchmark_test.go
b/arrow/array/binary_equality_benchmark_test.go
new file mode 100644
index 00000000..79cbaa38
--- /dev/null
+++ b/arrow/array/binary_equality_benchmark_test.go
@@ -0,0 +1,131 @@
+// 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 array_test
+
+import (
+ "fmt"
+ "testing"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/memory"
+)
+
+var binaryEqualityResult bool
+
+func BenchmarkBinaryEquality(b *testing.B) {
+ const length = 64 * 1024
+
+ types := []arrow.BinaryDataType{
+ arrow.BinaryTypes.Binary,
+ arrow.BinaryTypes.String,
+ arrow.BinaryTypes.LargeBinary,
+ arrow.BinaryTypes.LargeString,
+ }
+
+ for _, dtype := range types {
+ b.Run(dtype.Name(), func(b *testing.B) {
+ for _, valueLen := range []int{8, 32, 128, 1024} {
+ benchmarkBinaryEqualityCase(b, dtype, length,
valueLen, nil, "equal", -1)
+ }
+
+ for _, tc := range []struct {
+ name string
+ valid func(int) bool
+ mismatchIndex int
+ }{
+ {name: "nulls_10_percent", valid: func(i int)
bool { return i%10 != 0 }, mismatchIndex: -1},
+ {name: "nulls_50_percent", valid: func(i int)
bool { return i%2 != 0 }, mismatchIndex: -1},
+ {name: "nulls_50_percent_clustered", valid:
func(i int) bool { return i >= length/2 }, mismatchIndex: -1},
+ {name: "mismatch_first", mismatchIndex: 0},
+ {name: "mismatch_middle", mismatchIndex: length
/ 2},
+ {name: "mismatch_last", mismatchIndex: length -
1},
+ {name: "different_length", mismatchIndex:
length / 2},
+ } {
+ benchmarkBinaryEqualityCase(b, dtype, length,
32, tc.valid, tc.name, tc.mismatchIndex)
+ }
+ })
+ }
+}
+
+func BenchmarkBinaryEqualityShortArrays(b *testing.B) {
+ for _, length := range []int{4, 8, 16, 32, 64, 128} {
+ length := length
+ b.Run(fmt.Sprintf("length_%d", length), func(b *testing.B) {
+ benchmarkBinaryEqualityCase(
+ b,
+ arrow.BinaryTypes.String,
+ length,
+ 16,
+ func(i int) bool { return i%2 == 0 },
+ "alternating_nulls",
+ -1,
+ )
+ })
+ }
+}
+
+func benchmarkBinaryEqualityCase(
+ b *testing.B, dtype arrow.BinaryDataType, length, valueLen int,
validValue func(int) bool, name string, mismatchIndex int,
+) {
+ b.Helper()
+
+ values := makeBinaryEqualityValues(length, valueLen)
+ rightValues := append([]string(nil), values...)
+ valid := make([]bool, length)
+ for i := range valid {
+ valid[i] = validValue == nil || validValue(i)
+ }
+ if mismatchIndex >= 0 {
+ if name == "different_length" {
+ rightValues[mismatchIndex] += "x"
+ } else {
+ value := []byte(rightValues[mismatchIndex])
+ value[0]++
+ rightValues[mismatchIndex] = string(value)
+ }
+ }
+
+ mem := memory.NewGoAllocator()
+ left := makeBinaryEqualityArray(mem, dtype, values, valid)
+ right := makeBinaryEqualityArray(mem, dtype, rightValues, valid)
+ b.Cleanup(func() {
+ left.Release()
+ right.Release()
+ })
+
+ b.Run(fmt.Sprintf("%s/value_len_%d", name, valueLen), func(b
*testing.B) {
+ b.ReportAllocs()
+ b.SetBytes(int64(length * valueLen))
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ binaryEqualityResult = array.Equal(left, right)
+ }
+ })
+}
+
+func makeBinaryEqualityValues(length, valueLen int) []string {
+ values := make([]string, length)
+ value := make([]byte, valueLen)
+ for i := range values {
+ for j := range value {
+ value[j] = byte(i*31 + j*17)
+ }
+ values[i] = string(value)
+ }
+ return values
+}
diff --git a/arrow/array/binary_equality_test.go
b/arrow/array/binary_equality_test.go
new file mode 100644
index 00000000..05a56581
--- /dev/null
+++ b/arrow/array/binary_equality_test.go
@@ -0,0 +1,444 @@
+// 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 array_test
+
+import (
+ "testing"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/bitutil"
+ "github.com/apache/arrow-go/v18/arrow/memory"
+ "github.com/stretchr/testify/assert"
+ "github.com/stretchr/testify/require"
+)
+
+func TestBinaryEqualityByValidRuns(t *testing.T) {
+ types := []arrow.BinaryDataType{
+ arrow.BinaryTypes.Binary,
+ arrow.BinaryTypes.String,
+ arrow.BinaryTypes.LargeBinary,
+ arrow.BinaryTypes.LargeString,
+ }
+ tests := []struct {
+ name string
+ left []string
+ right []string
+ valid []bool
+ want bool
+ leftSlice [2]int64
+ rightSlice [2]int64
+ }{
+ {
+ name: "equal values",
+ left: []string{"alpha", "beta", "gamma"},
+ right: []string{"alpha", "beta", "gamma"},
+ valid: []bool{true, true, true},
+ want: true,
+ },
+ {
+ name: "different payload",
+ left: []string{"alpha", "beta", "gamma"},
+ right: []string{"alpha", "zeta", "gamma"},
+ valid: []bool{true, true, true},
+ },
+ {
+ name: "same payload with different boundaries",
+ left: []string{"ab", "c"},
+ right: []string{"a", "bc"},
+ valid: []bool{true, true},
+ },
+ {
+ name: "null payload ignored",
+ left: []string{"alpha", "ignored left", "gamma"},
+ right: []string{"alpha", "ignored right payload",
"gamma"},
+ valid: []bool{true, false, true},
+ want: true,
+ },
+ {
+ name: "different physical offsets",
+ left: []string{"left prefix", "alpha", "beta",
"left suffix"},
+ right: []string{"right prefix 1", "right prefix
2", "alpha", "beta"},
+ valid: []bool{true, true, true, true},
+ want: true,
+ leftSlice: [2]int64{1, 3},
+ rightSlice: [2]int64{2, 4},
+ },
+ }
+
+ for _, dtype := range types {
+ t.Run(dtype.Name(), func(t *testing.T) {
+ for _, test := range tests {
+ t.Run(test.name, func(t *testing.T) {
+ left :=
makeBinaryEqualityArray(memory.DefaultAllocator, dtype, test.left, test.valid)
+ defer left.Release()
+ right :=
makeBinaryEqualityArray(memory.DefaultAllocator, dtype, test.right, test.valid)
+ defer right.Release()
+
+ if test.leftSlice != [2]int64{} {
+ leftSlice :=
array.NewSlice(left, test.leftSlice[0], test.leftSlice[1])
+ defer leftSlice.Release()
+ rightSlice :=
array.NewSlice(right, test.rightSlice[0], test.rightSlice[1])
+ defer rightSlice.Release()
+ left, right = leftSlice,
rightSlice
+ }
+
+ assert.Equal(t, test.want,
array.Equal(left, right))
+ })
+ }
+ })
+ }
+}
+
+func TestBinaryEqualityByValidRunsAcrossNulls(t *testing.T) {
+ const length = 256
+
+ types := []arrow.BinaryDataType{
+ arrow.BinaryTypes.Binary,
+ arrow.BinaryTypes.String,
+ arrow.BinaryTypes.LargeBinary,
+ arrow.BinaryTypes.LargeString,
+ }
+ valid := makeLongValidRuns(length)
+ tests := []struct {
+ name string
+ build func(arrow.BinaryDataType) (arrow.Array, arrow.Array)
+ want bool
+ }{
+ {
+ name: "equal arrays with long valid runs",
+ build: func(dtype arrow.BinaryDataType) (arrow.Array,
arrow.Array) {
+ values := makeBinaryEqualityValues(length, 16)
+ return
makeBinaryEqualityArray(memory.DefaultAllocator, dtype, values, valid),
+
makeBinaryEqualityArray(memory.DefaultAllocator, dtype, values, valid)
+ },
+ want: true,
+ },
+ {
+ name: "different bytes under null slots are ignored",
+ build: func(dtype arrow.BinaryDataType) (arrow.Array,
arrow.Array) {
+ leftValues := makeBinaryEqualityValues(length,
16)
+ rightValues := append([]string(nil),
leftValues...)
+ for i, isValid := range valid {
+ if !isValid {
+ rightValues[i] = "different
ignored payload"
+ }
+ }
+ return makeRawBinaryEqualityArray(dtype,
leftValues, valid),
+ makeRawBinaryEqualityArray(dtype,
rightValues, valid)
+ },
+ want: true,
+ },
+ {
+ name: "mismatch in a later valid run",
+ build: func(dtype arrow.BinaryDataType) (arrow.Array,
arrow.Array) {
+ leftValues := makeBinaryEqualityValues(length,
16)
+ rightValues := append([]string(nil),
leftValues...)
+ value := []byte(rightValues[192])
+ value[0]++
+ rightValues[192] = string(value)
+ return
makeBinaryEqualityArray(memory.DefaultAllocator, dtype, leftValues, valid),
+
makeBinaryEqualityArray(memory.DefaultAllocator, dtype, rightValues, valid)
+ },
+ },
+ {
+ name: "different physical offsets with nulls",
+ build: makeSlicedBinaryEqualityPair,
+ want: true,
+ },
+ {
+ name: "shifted value boundary inside a valid run",
+ build: func(dtype arrow.BinaryDataType) (arrow.Array,
arrow.Array) {
+ const length = 192
+ valid := make([]bool, length)
+ for i := range valid {
+ valid[i] = i < 128
+ }
+
+ leftValues := makeBinaryEqualityValues(length,
16)
+ rightValues := append([]string(nil),
leftValues...)
+ leftValues[64], leftValues[65] = "ab", "c"
+ rightValues[64], rightValues[65] = "a", "bc"
+ return
makeBinaryEqualityArray(memory.DefaultAllocator, dtype, leftValues, valid),
+
makeBinaryEqualityArray(memory.DefaultAllocator, dtype, rightValues, valid)
+ },
+ },
+ }
+
+ for _, dtype := range types {
+ t.Run(dtype.Name(), func(t *testing.T) {
+ for _, test := range tests {
+ t.Run(test.name, func(t *testing.T) {
+ left, right := test.build(dtype)
+ defer left.Release()
+ defer right.Release()
+
+ assert.Equal(t, test.want,
array.Equal(left, right))
+ })
+ }
+ })
+ }
+}
+
+func TestBinaryEqualityWithFragmentedValidity(t *testing.T) {
+ const length = 1024
+ leftValues := makeBinaryEqualityValues(length, 16)
+ rightValues := append([]string(nil), leftValues...)
+ valid := make([]bool, length)
+ for i := range valid {
+ valid[i] = i%2 == 0
+ if !valid[i] {
+ rightValues[i] = "different ignored payload"
+ }
+ }
+
+ left := makeBinaryEqualityArray(memory.DefaultAllocator,
arrow.BinaryTypes.String, leftValues, valid)
+ defer left.Release()
+ right := makeBinaryEqualityArray(memory.DefaultAllocator,
arrow.BinaryTypes.String, rightValues, valid)
+ require.True(t, array.Equal(left, right))
+
+ right.Release()
+ rightValues[length-2] = "different valid payload"
+ right = makeBinaryEqualityArray(memory.DefaultAllocator,
arrow.BinaryTypes.String, rightValues, valid)
+ defer right.Release()
+ require.False(t, array.Equal(left, right))
+}
+
+func TestBinaryEqualityWithDeclaredNullsWithoutBitmap(t *testing.T) {
+ makeArray := func() *array.Binary {
+ const length = 128
+ offsets := make([]int32, length+1)
+ values := make([]byte, length)
+ for i := range values {
+ offsets[i] = int32(i)
+ values[i] = byte('a' + i%26)
+ }
+ offsets[length] = int32(length)
+
+ offsetsBuffer :=
memory.NewBufferBytes(arrow.Int32Traits.CastToBytes(offsets))
+ valuesBuffer := memory.NewBufferBytes(values)
+ data := array.NewData(
+ arrow.BinaryTypes.Binary,
+ length,
+ []*memory.Buffer{nil, offsetsBuffer, valuesBuffer},
+ nil,
+ 1,
+ 0,
+ )
+ offsetsBuffer.Release()
+ valuesBuffer.Release()
+ result := array.NewBinaryData(data)
+ data.Release()
+ return result
+ }
+
+ left := makeArray()
+ defer left.Release()
+ right := makeArray()
+ defer right.Release()
+
+ var equal bool
+ assert.NotPanics(t, func() { equal = array.Equal(left, right) })
+ assert.True(t, equal)
+}
+
+func TestBinaryEqualityWithBitmapAndZeroDeclaredNulls(t *testing.T) {
+ const length = 128
+ valid := makeLongValidRuns(length)
+ leftValues := makeBinaryEqualityValues(length, 16)
+ rightValues := append([]string(nil), leftValues...)
+ for i, isValid := range valid {
+ if !isValid {
+ rightValues[i] = "different ignored payload"
+ }
+ }
+
+ for _, dtype := range []arrow.BinaryDataType{
+ arrow.BinaryTypes.Binary,
+ arrow.BinaryTypes.String,
+ arrow.BinaryTypes.LargeBinary,
+ arrow.BinaryTypes.LargeString,
+ } {
+ t.Run(dtype.Name(), func(t *testing.T) {
+ left := makeRawBinaryEqualityArrayWithNullCount(dtype,
leftValues, valid, 0)
+ defer left.Release()
+ right := makeRawBinaryEqualityArrayWithNullCount(dtype,
rightValues, valid, 0)
+ defer right.Release()
+
+ assert.True(t, array.Equal(left, right))
+ })
+ }
+}
+
+func TestBinaryEqualityEmptyArraysWithoutOffsets(t *testing.T) {
+ for _, dtype := range []arrow.BinaryDataType{
+ arrow.BinaryTypes.Binary,
+ arrow.BinaryTypes.String,
+ arrow.BinaryTypes.LargeBinary,
+ arrow.BinaryTypes.LargeString,
+ } {
+ t.Run(dtype.Name(), func(t *testing.T) {
+ makeArray := func() arrow.Array {
+ data := array.NewData(dtype, 0,
[]*memory.Buffer{nil, nil, nil}, nil, 0, 0)
+ result := array.MakeFromData(data)
+ data.Release()
+ return result
+ }
+
+ left := makeArray()
+ defer left.Release()
+ right := makeArray()
+ defer right.Release()
+
+ assert.NotPanics(t, func() {
+ assert.True(t, array.Equal(left, right))
+ })
+ })
+ }
+}
+
+func makeLongValidRuns(length int) []bool {
+ valid := make([]bool, length)
+ for i := range valid {
+ valid[i] = (i/8)%2 == 0
+ }
+ return valid
+}
+
+func makeSlicedBinaryEqualityPair(dtype arrow.BinaryDataType) (arrow.Array,
arrow.Array) {
+ const (
+ length = 256
+ leftOffset = 5
+ rightOffset = 17
+ )
+
+ logicalValues := makeBinaryEqualityValues(length, 16)
+ logicalValid := makeLongValidRuns(length)
+ leftValues := makeBinaryEqualityValues(leftOffset+length+1, 16)
+ rightValues := makeBinaryEqualityValues(rightOffset+length+1, 16)
+ leftValid := make([]bool, len(leftValues))
+ rightValid := make([]bool, len(rightValues))
+ for i := range logicalValues {
+ leftValues[leftOffset+i] = logicalValues[i]
+ rightValues[rightOffset+i] = logicalValues[i]
+ leftValid[leftOffset+i] = logicalValid[i]
+ rightValid[rightOffset+i] = logicalValid[i]
+ }
+
+ leftBase := makeBinaryEqualityArray(memory.DefaultAllocator, dtype,
leftValues, leftValid)
+ left := array.NewSlice(leftBase, leftOffset, leftOffset+length)
+ leftBase.Release()
+ rightBase := makeBinaryEqualityArray(memory.DefaultAllocator, dtype,
rightValues, rightValid)
+ right := array.NewSlice(rightBase, rightOffset, rightOffset+length)
+ rightBase.Release()
+ return left, right
+}
+
+func makeRawBinaryEqualityArray(dtype arrow.BinaryDataType, values []string,
valid []bool) arrow.Array {
+ nulls := 0
+ for _, isValid := range valid {
+ if !isValid {
+ nulls++
+ }
+ }
+ return makeRawBinaryEqualityArrayWithNullCount(dtype, values, valid,
nulls)
+}
+
+func makeRawBinaryEqualityArrayWithNullCount(
+ dtype arrow.BinaryDataType, values []string, valid []bool, nulls int,
+) arrow.Array {
+ if len(values) != len(valid) {
+ panic("len(values) != len(valid)")
+ }
+
+ valueBytes := make([]byte, 0)
+ var offsetBytes []byte
+ switch dtype.ID() {
+ case arrow.BINARY, arrow.STRING:
+ offsets := make([]int32, len(values)+1)
+ for i, value := range values {
+ offsets[i] = int32(len(valueBytes))
+ valueBytes = append(valueBytes, value...)
+ }
+ offsets[len(values)] = int32(len(valueBytes))
+ offsetBytes = arrow.Int32Traits.CastToBytes(offsets)
+ case arrow.LARGE_BINARY, arrow.LARGE_STRING:
+ offsets := make([]int64, len(values)+1)
+ for i, value := range values {
+ offsets[i] = int64(len(valueBytes))
+ valueBytes = append(valueBytes, value...)
+ }
+ offsets[len(values)] = int64(len(valueBytes))
+ offsetBytes = arrow.Int64Traits.CastToBytes(offsets)
+ default:
+ panic("unsupported binary type")
+ }
+
+ validity := make([]byte, (len(valid)+7)/8)
+ for i, isValid := range valid {
+ if isValid {
+ bitutil.SetBit(validity, i)
+ }
+ }
+
+ validityBuffer := memory.NewBufferBytes(validity)
+ offsetsBuffer := memory.NewBufferBytes(offsetBytes)
+ valuesBuffer := memory.NewBufferBytes(valueBytes)
+ data := array.NewData(
+ dtype,
+ len(values),
+ []*memory.Buffer{validityBuffer, offsetsBuffer, valuesBuffer},
+ nil,
+ nulls,
+ 0,
+ )
+ validityBuffer.Release()
+ offsetsBuffer.Release()
+ valuesBuffer.Release()
+ result := array.MakeFromData(data)
+ data.Release()
+ return result
+}
+
+func makeBinaryEqualityArray(
+ mem memory.Allocator, dtype arrow.BinaryDataType, values []string,
valid []bool,
+) arrow.Array {
+ switch dtype.ID() {
+ case arrow.BINARY:
+ builder := array.NewBinaryBuilder(mem, dtype)
+ defer builder.Release()
+ builder.AppendStringValues(values, valid)
+ return builder.NewBinaryArray()
+ case arrow.STRING:
+ builder := array.NewStringBuilder(mem)
+ defer builder.Release()
+ builder.AppendValues(values, valid)
+ return builder.NewStringArray()
+ case arrow.LARGE_BINARY:
+ builder := array.NewBinaryBuilder(mem, dtype)
+ defer builder.Release()
+ builder.AppendStringValues(values, valid)
+ return builder.NewLargeBinaryArray()
+ case arrow.LARGE_STRING:
+ builder := array.NewLargeStringBuilder(mem)
+ defer builder.Release()
+ builder.AppendValues(values, valid)
+ return builder.NewLargeStringArray()
+ default:
+ panic("unsupported binary type")
+ }
+}
diff --git a/arrow/array/string.go b/arrow/array/string.go
index afd78278..e230fa17 100644
--- a/arrow/array/string.go
+++ b/arrow/array/string.go
@@ -239,15 +239,21 @@ func (a *String) ValidateFull() error {
}
func arrayEqualString(left, right *String) bool {
- for i := 0; i < left.Len(); i++ {
- if left.IsNull(i) {
- continue
- }
- if left.Value(i) != right.Value(i) {
- return false
+ if useScalarVariableWidthEquality(left) {
+ for i := range left.Len() {
+ if !left.IsNull(i) && left.Value(i) != right.Value(i) {
+ return false
+ }
}
+ return true
}
- return true
+ return arrayEqualVariableWidth(
+ left.offsets, right.offsets,
+ left.values, right.values,
+ left.Offset(), right.Offset(), left.Len(),
+ left.NullN(), left.NullBitmapBytes(),
+ equalStrings,
+ )
}
// String represents an immutable sequence of variable-length UTF-8 strings.
@@ -450,15 +456,25 @@ func (a *LargeString) ValidateFull() error {
}
func arrayEqualLargeString(left, right *LargeString) bool {
- for i := 0; i < left.Len(); i++ {
- if left.IsNull(i) {
- continue
- }
- if left.Value(i) != right.Value(i) {
- return false
+ if useScalarVariableWidthEquality(left) {
+ for i := range left.Len() {
+ if !left.IsNull(i) && left.Value(i) != right.Value(i) {
+ return false
+ }
}
+ return true
}
- return true
+ return arrayEqualVariableWidth(
+ left.offsets, right.offsets,
+ left.values, right.values,
+ left.Offset(), right.Offset(), left.Len(),
+ left.NullN(), left.NullBitmapBytes(),
+ equalStrings,
+ )
+}
+
+func equalStrings(left, right string) bool {
+ return left == right
}
type StringView struct {
