You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "zeroshade (via GitHub)" <gi...@apache.org> on 2026/04/07 21:41:12 UTC
Re: [PR] feat(arrow/compute): sort support [arrow-go]
zeroshade commented on code in PR #749:
URL: https://github.com/apache/arrow-go/pull/749#discussion_r3047657285
##########
arrow/compute/internal/kernels/vector_sort.go:
##########
@@ -0,0 +1,476 @@
+// 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.
+
+//go:build go1.18
+
+package kernels
+
+import (
+ "fmt"
+ "slices"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/compute/exec"
+)
+
+// SortOrder specifies the sort order for sorting operations.
+type SortOrder int8
+
+const (
+ Ascending SortOrder = iota
+ Descending
+)
+
+// NullPlacement specifies where null values should be placed in the sort order.
+type NullPlacement int8
+
+const (
+ NullsAtEnd NullPlacement = iota
+ NullsAtStart
+)
+
+// SortOptions defines options for the sort_indices function.
+type SortOptions struct {
+ Order SortOrder `compute:"order"`
+ NullPlacement NullPlacement `compute:"null_placement"`
+}
Review Comment:
the `compute` struct tags are unnecessary as there is no longer anything that expects them or will use them.
##########
arrow/compute/internal/kernels/vector_sort.go:
##########
@@ -0,0 +1,476 @@
+// 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.
+
+//go:build go1.18
+
+package kernels
+
+import (
+ "fmt"
+ "slices"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/compute/exec"
+)
+
+// SortOrder specifies the sort order for sorting operations.
+type SortOrder int8
+
+const (
+ Ascending SortOrder = iota
+ Descending
+)
+
+// NullPlacement specifies where null values should be placed in the sort order.
+type NullPlacement int8
+
+const (
+ NullsAtEnd NullPlacement = iota
+ NullsAtStart
+)
+
+// SortOptions defines options for the sort_indices function.
+type SortOptions struct {
+ Order SortOrder `compute:"order"`
+ NullPlacement NullPlacement `compute:"null_placement"`
+}
+
+func (SortOptions) TypeName() string { return "SortOptions" }
+
+type SortState = SortOptions
+
+// SortKey defines a column to sort by with its ordering and null placement options.
+type SortKey struct {
+ ColumnIndex int
+ Order SortOrder
+ NullPlacement NullPlacement
+}
+
+// Chunk-aware sort_indices: logical row IDs 0..n-1, no chunk concatenation. Structure follows
+// Apache Arrow C++ vector_sort.cc / vector_sort_internal.h (see vector_sort_internal.go).
+//
+// Per-column data uses a dense logicalRowMap for O(1) chunk resolution under random compares.
+// Each sortable physical type has a dedicated comparator struct in vector_sort_physical.go (C++
+// ConcreteColumnComparator<T> shape): full monomorphization for the hot compare path; no
+// value-level compare func pointer.
+// compareRowsForKey implements the same ordering as C++ (null placement, NaN, Order).
+//
+// Single key: ChunkedArraySorter — arraySortOneColumnRange per chunk (PartitionNullsOnly /
+// PartitionNullLikes + stable_sort finites), then pairwise merge (ChunkedMergeImpl-style merge
+// using full row order; C++ splits null / non-null merge when the type has null-likes).
+//
+// Multi-key, aligned chunks: TableSorter — per-chunk RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter, then merge.
+//
+// Multi-key, single segment: RadixRecordBatchSorter (<= maxRadixSortKeys) or
+// MultipleKeyRecordBatchSorter (> maxRadixSortKeys).
+
+// maxRadixSortKeys matches Arrow C++ kMaxRadixSortKeys (vector_sort.cc): above this, one global
+// multi-key stable sort is used instead of MSD radix.
+const maxRadixSortKeys = 8
+
+// columnComparator is the Go analogue of compute::internal::ColumnComparator (vector_sort_internal.h):
+// per-column row compare + null / null-like metadata for partitioning.
+type columnComparator interface {
+ // compareRowsForKey returns -1 if i before j, +1 if i after j, 0 if tied on this column
+ // (both null, or both non-null and equal), so the caller may advance to the next sort key.
+ compareRowsForKey(i, j uint64, key SortKey) int
+ // isNullAt returns true if the global row index is null.
+ isNullAt(global uint64) bool
+ // hasNullLikeValues returns true if the column has null-like values.
+ hasNullLikeValues() bool
+ // isNullLikeAt returns true if the global row index is a null-like value.
+ isNullLikeAt(global uint64) bool
+ // columnHasValidityNulls mirrors Array::null_count() != 0; when false, C++ skips PartitionNullsOnly.
+ columnHasValidityNulls() bool
+}
+
+// multiColumnComparator compares two logical rows (global uint64 indices) lexicographically
+// across every sort key. That matches C++ MultipleKeyComparator::CompareInternal(left, right, 0)
+// (vector_sort_internal.h), but it is not a port of the whole MultipleKeyComparator type: C++ keeps
+// ResolvedSortKey per column, uses Location (int64 batch row vs ChunkLocation on tables), builds
+// virtual ColumnComparator instances, and passes start_sort_key_index for radix tails and other
+// partial key ranges — in Go those suffix compares are makeTailComparator(comparators, keys, from).
+type multiColumnComparator struct {
+ columns []columnComparator
+ keys []SortKey
+}
+
+// compare is a three-way ordering for stable sort / merge: negative if idxA before idxB, etc.
+func (m *multiColumnComparator) compare(idxA, idxB uint64) int {
+ for i, key := range m.keys {
+ if cmpVal := m.columns[i].compareRowsForKey(idxA, idxB, key); cmpVal != 0 {
+ return cmpVal
+ }
+ }
+ return 0
+}
+
+func extensionStorageFixedSizeBinaryChunks(chunks []arrow.Array) ([]arrow.Array, error) {
+ out := make([]arrow.Array, len(chunks))
+ for i, ch := range chunks {
+ ext, ok := ch.(array.ExtensionArray)
+ if !ok {
+ return nil, fmt.Errorf("%w: extension column must implement array.ExtensionArray", arrow.ErrInvalid)
+ }
+ st := ext.Storage()
+ if st.DataType().ID() != arrow.FIXED_SIZE_BINARY {
Review Comment:
this is fine for now, but we might want to enable individual extension types to allow specifying how to sort themselves properly, let's leave a TODO here.
##########
arrow/compute/internal/kernels/vector_sort.go:
##########
@@ -0,0 +1,476 @@
+// 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.
+
+//go:build go1.18
+
+package kernels
+
+import (
+ "fmt"
+ "slices"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/compute/exec"
+)
+
+// SortOrder specifies the sort order for sorting operations.
+type SortOrder int8
+
+const (
+ Ascending SortOrder = iota
+ Descending
+)
+
+// NullPlacement specifies where null values should be placed in the sort order.
+type NullPlacement int8
+
+const (
+ NullsAtEnd NullPlacement = iota
+ NullsAtStart
+)
+
+// SortOptions defines options for the sort_indices function.
+type SortOptions struct {
+ Order SortOrder `compute:"order"`
+ NullPlacement NullPlacement `compute:"null_placement"`
+}
+
+func (SortOptions) TypeName() string { return "SortOptions" }
+
+type SortState = SortOptions
+
+// SortKey defines a column to sort by with its ordering and null placement options.
+type SortKey struct {
+ ColumnIndex int
+ Order SortOrder
+ NullPlacement NullPlacement
+}
+
+// Chunk-aware sort_indices: logical row IDs 0..n-1, no chunk concatenation. Structure follows
+// Apache Arrow C++ vector_sort.cc / vector_sort_internal.h (see vector_sort_internal.go).
+//
+// Per-column data uses a dense logicalRowMap for O(1) chunk resolution under random compares.
+// Each sortable physical type has a dedicated comparator struct in vector_sort_physical.go (C++
+// ConcreteColumnComparator<T> shape): full monomorphization for the hot compare path; no
+// value-level compare func pointer.
+// compareRowsForKey implements the same ordering as C++ (null placement, NaN, Order).
+//
+// Single key: ChunkedArraySorter — arraySortOneColumnRange per chunk (PartitionNullsOnly /
+// PartitionNullLikes + stable_sort finites), then pairwise merge (ChunkedMergeImpl-style merge
+// using full row order; C++ splits null / non-null merge when the type has null-likes).
+//
+// Multi-key, aligned chunks: TableSorter — per-chunk RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter, then merge.
+//
+// Multi-key, single segment: RadixRecordBatchSorter (<= maxRadixSortKeys) or
+// MultipleKeyRecordBatchSorter (> maxRadixSortKeys).
+
+// maxRadixSortKeys matches Arrow C++ kMaxRadixSortKeys (vector_sort.cc): above this, one global
+// multi-key stable sort is used instead of MSD radix.
+const maxRadixSortKeys = 8
+
+// columnComparator is the Go analogue of compute::internal::ColumnComparator (vector_sort_internal.h):
+// per-column row compare + null / null-like metadata for partitioning.
+type columnComparator interface {
+ // compareRowsForKey returns -1 if i before j, +1 if i after j, 0 if tied on this column
+ // (both null, or both non-null and equal), so the caller may advance to the next sort key.
+ compareRowsForKey(i, j uint64, key SortKey) int
+ // isNullAt returns true if the global row index is null.
+ isNullAt(global uint64) bool
+ // hasNullLikeValues returns true if the column has null-like values.
+ hasNullLikeValues() bool
+ // isNullLikeAt returns true if the global row index is a null-like value.
+ isNullLikeAt(global uint64) bool
+ // columnHasValidityNulls mirrors Array::null_count() != 0; when false, C++ skips PartitionNullsOnly.
+ columnHasValidityNulls() bool
+}
+
+// multiColumnComparator compares two logical rows (global uint64 indices) lexicographically
+// across every sort key. That matches C++ MultipleKeyComparator::CompareInternal(left, right, 0)
+// (vector_sort_internal.h), but it is not a port of the whole MultipleKeyComparator type: C++ keeps
+// ResolvedSortKey per column, uses Location (int64 batch row vs ChunkLocation on tables), builds
+// virtual ColumnComparator instances, and passes start_sort_key_index for radix tails and other
+// partial key ranges — in Go those suffix compares are makeTailComparator(comparators, keys, from).
+type multiColumnComparator struct {
+ columns []columnComparator
+ keys []SortKey
+}
+
+// compare is a three-way ordering for stable sort / merge: negative if idxA before idxB, etc.
+func (m *multiColumnComparator) compare(idxA, idxB uint64) int {
+ for i, key := range m.keys {
+ if cmpVal := m.columns[i].compareRowsForKey(idxA, idxB, key); cmpVal != 0 {
+ return cmpVal
+ }
+ }
+ return 0
+}
+
+func extensionStorageFixedSizeBinaryChunks(chunks []arrow.Array) ([]arrow.Array, error) {
+ out := make([]arrow.Array, len(chunks))
+ for i, ch := range chunks {
+ ext, ok := ch.(array.ExtensionArray)
+ if !ok {
+ return nil, fmt.Errorf("%w: extension column must implement array.ExtensionArray", arrow.ErrInvalid)
+ }
+ st := ext.Storage()
+ if st.DataType().ID() != arrow.FIXED_SIZE_BINARY {
+ return nil, fmt.Errorf("%w: sorting extension columns is only supported when storage is fixed_size_binary (got %s)",
+ arrow.ErrNotImplemented, st.DataType())
+ }
+ out[i] = st
+ }
+ return out, nil
+}
+
+func newFixedSizeBinaryComparator(chunks []arrow.Array, numRows int, vn bool) (columnComparator, error) {
+ f0, ok := chunks[0].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ w := f0.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ for i := 1; i < len(chunks); i++ {
+ fi, ok := chunks[i].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ wi := fi.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ if wi != w {
+ return nil, fmt.Errorf("%w: fixed_size_binary chunks must have the same byte width (%d vs %d)",
+ arrow.ErrInvalid, w, wi)
+ }
+ }
+ return newPhysicalSortFixedSizeBinaryColumn(chunks, numRows, vn), nil
+}
+
+// createChunkedComparator builds a column comparator for these chunks (one Arrow type for all chunks).
+func createChunkedComparator(chunks []arrow.Array, numRows int) (columnComparator, error) {
+ if len(chunks) == 0 {
+ return nil, fmt.Errorf("%w: cannot create comparator for empty chunk list", arrow.ErrInvalid)
+ }
+ if totalChunkRows(chunks) != numRows {
+ return nil, fmt.Errorf("%w: chunk row count does not match column length", arrow.ErrInvalid)
+ }
+
+ validityNulls := chunksHaveNulls(chunks)
+ typeID := chunks[0].DataType().ID()
+ switch typeID {
+ case arrow.INT8:
+ return newPhysicalSortInt8Column(chunks, numRows, validityNulls), nil
+ case arrow.INT16:
+ return newPhysicalSortInt16Column(chunks, numRows, validityNulls), nil
+ case arrow.INT32:
+ return newPhysicalSortInt32Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE32:
+ return newPhysicalSortDate32Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME32:
+ return newPhysicalSortTime32Column(chunks, numRows, validityNulls), nil
+ case arrow.INT64:
+ return newPhysicalSortInt64Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE64:
+ return newPhysicalSortDate64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME64:
+ return newPhysicalSortTime64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIMESTAMP:
+ return newPhysicalSortTimestampColumn(chunks, numRows, validityNulls), nil
+ case arrow.DURATION:
+ return newPhysicalSortDurationColumn(chunks, numRows, validityNulls), nil
+ case arrow.UINT8:
+ return newPhysicalSortUint8Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT16:
+ return newPhysicalSortUint16Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT32:
+ return newPhysicalSortUint32Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT64:
+ return newPhysicalSortUint64Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT16:
+ return newPhysicalSortFloat16Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT32:
+ return newPhysicalSortFloat32Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT64:
+ return newPhysicalSortFloat64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL32:
+ return newPhysicalSortDecimal32Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL64:
+ return newPhysicalSortDecimal64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL128:
+ return newPhysicalSortDecimal128Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL256:
+ return newPhysicalSortDecimal256Column(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTHS:
+ return newPhysicalSortMonthIntervalColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_DAY_TIME:
+ return newPhysicalSortDayTimeColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTH_DAY_NANO:
+ return newPhysicalSortMonthDayNanoColumn(chunks, numRows, validityNulls), nil
+ case arrow.BOOL:
+ return newPhysicalSortBoolColumn(chunks, numRows, validityNulls), nil
+ case arrow.STRING:
+ return newPhysicalSortStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_STRING:
+ return newPhysicalSortLargeStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.BINARY:
+ return newPhysicalSortBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_BINARY:
+ return newPhysicalSortLargeBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.FIXED_SIZE_BINARY:
+ return newFixedSizeBinaryComparator(chunks, numRows, validityNulls)
+ case arrow.EXTENSION:
+ storageChunks, err := extensionStorageFixedSizeBinaryChunks(chunks)
+ if err != nil {
+ return nil, err
+ }
+ return newFixedSizeBinaryComparator(storageChunks, numRows, validityNulls)
+ default:
+ return nil, fmt.Errorf("%w: sorting not supported for type %s", arrow.ErrNotImplemented, typeID)
+ }
+}
+
+// chunkIndexSpan represents a contiguous range of indices in the global order.
+type chunkIndexSpan struct {
+ lo, hi int
+}
+
+// mergeAdjacentStable merges sorted adjacent ranges [a0,a1) and [b0,b1) (a1 == b0) into indices[lo:hi]
+// using a strict weak order: i is ordered before j iff less(i,j). Tie-breaking prefers the left range
+// (stable merge, same as C++ std::merge with !comp(right,left)).
+func mergeAdjacentStable(indices, tmp []uint64, a0, a1, b0, b1 int, less func(a, b uint64) bool) {
+ i, j, k := a0, b0, a0
+ for i < a1 && j < b1 {
+ if !less(indices[j], indices[i]) {
+ tmp[k] = indices[i]
+ i++
+ } else {
+ tmp[k] = indices[j]
+ j++
+ }
+ k++
+ }
+ for i < a1 {
+ tmp[k] = indices[i]
+ k++
+ i++
+ }
+ for j < b1 {
+ tmp[k] = indices[j]
+ k++
+ j++
+ }
+ copy(indices[a0:b1], tmp[a0:b1])
+}
+
+// pairwiseMergeSortedSpans merges already-sorted adjacent index spans (chunk batch rows in global
+// order), matching Arrow C++ ChunkedMergeImpl / TableSorter batch merge (vector_sort.cc).
+// spanScratch must have capacity >= len(spans); it ping-pongs with spans' backing during merging.
+func pairwiseMergeSortedSpans(indices, tmp []uint64, spans []chunkIndexSpan, less func(a, b uint64) bool, spanScratch []chunkIndexSpan) {
+ if len(spans) <= 1 {
+ return
+ }
+ if cap(spanScratch) < len(spans) {
+ panic("kernels: spanScratch cap < len(spans)")
+ }
+ cur := spans
+ other := spanScratch[:0]
+ for len(cur) > 1 {
+ other = other[:0]
+ for i := 0; i < len(cur); i += 2 {
+ if i+1 < len(cur) {
+ s0, s1 := cur[i], cur[i+1]
+ mergeAdjacentStable(indices, tmp, s0.lo, s0.hi, s1.lo, s1.hi, less)
+ other = append(other, chunkIndexSpan{s0.lo, s1.hi})
+ } else {
+ other = append(other, cur[i])
+ }
+ }
+ cur, other = other, cur
+ }
+}
+
+// alignedChunkBoundaries reports cumulative row offsets for chunk boundaries when every sort column
+// has the same chunk count and matching chunk lengths (typical for Arrow tables).
+func alignedChunkBoundaries(columns []*arrow.Chunked) ([]int, bool) {
+ if len(columns) == 0 {
+ return nil, false
+ }
+ ch0 := columns[0].Chunks()
+ n := len(ch0)
+ if n == 0 {
+ return nil, false
+ }
+ offs := make([]int, n+1)
+ for i := 0; i < n; i++ {
+ L := ch0[i].Len()
+ for j := 1; j < len(columns); j++ {
+ cj := columns[j].Chunks()
+ if len(cj) != n || cj[i].Len() != L {
+ return nil, false
+ }
+ }
+ offs[i+1] = offs[i] + L
+ }
+ if offs[n] != columns[0].Len() {
+ return nil, false
+ }
+ return offs, true
+}
+
+// sortIndicesSingleColumnChunked implements Arrow C++ ChunkedArraySorter for one logical column:
+// per-chunk array sort (partition + sort finites), then pairwise merge (ChunkedMergeImpl).
+func sortIndicesSingleColumnChunked(indices []uint64, chunks []arrow.Array, comp columnComparator, key SortKey, tmp []uint64, spanScratch []chunkIndexSpan) {
+ lo := 0
+ for _, ch := range chunks {
+ hi := lo + ch.Len()
+ arraySortOneColumnRange(indices, tmp, comp, key, lo, hi)
+ lo = hi
+ }
+
+ nChunks := len(chunks)
+ if nChunks <= 1 {
+ return
+ }
+
+ less := func(a, b uint64) bool { return comp.compareRowsForKey(a, b, key) < 0 }
+
+ spans := make([]chunkIndexSpan, nChunks)
+ lo = 0
+ for i, ch := range chunks {
+ hi := lo + ch.Len()
+ spans[i] = chunkIndexSpan{lo, hi}
+ lo = hi
+ }
+ pairwiseMergeSortedSpans(indices, tmp, spans, less, spanScratch)
+}
+
+// sortIndicesMultiColumnAlignedChunks sorts each aligned chunk (C++ RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter), then merges like Arrow C++ TableSorter.
+func sortIndicesMultiColumnAlignedChunks(indices []uint64, offs []int, comparators []columnComparator, keys []SortKey, multiComp *multiColumnComparator, tmp []uint64, spanScratch []chunkIndexSpan) {
+ nChunks := len(offs) - 1
+ useRadix := len(keys) <= maxRadixSortKeys
+ for c := 0; c < nChunks; c++ {
+ lo, hi := offs[c], offs[c+1]
+ if useRadix {
+ radixRecordBatchSortRange(indices, tmp, comparators, keys, 0, lo, hi)
+ } else {
+ multipleKeyRecordBatchSortRange(indices, tmp, comparators, keys, lo, hi, makeTailComparator(comparators, keys, 1))
+ }
+ }
+ if nChunks <= 1 {
+ return
+ }
+ less := func(a, b uint64) bool { return multiComp.compare(a, b) < 0 }
+ spans := make([]chunkIndexSpan, nChunks)
+ for c := 0; c < nChunks; c++ {
+ spans[c] = chunkIndexSpan{offs[c], offs[c+1]}
+ }
+ pairwiseMergeSortedSpans(indices, tmp, spans, less, spanScratch)
+}
+
+// SortIndices returns a stable permutation of 0..n-1 that would lexicographically sort the given
+// columns. Each *arrow.Chunked is used via its .Chunks() only—no concatenate. columns[i] pairs with
+// keys[i] for order and null placement on that column.
+func SortIndices(ctx *exec.KernelCtx, columns []*arrow.Chunked, keys []SortKey) (*exec.ExecResult, error) {
+ if len(columns) == 0 || len(keys) == 0 {
+ return nil, fmt.Errorf("%w: must have at least one column and one sort key", arrow.ErrInvalid)
+ }
+
+ if len(columns) != len(keys) {
+ return nil, fmt.Errorf("%w: number of columns (%d) must match number of sort keys (%d)",
+ arrow.ErrInvalid, len(columns), len(keys))
+ }
+
+ length := int64(columns[0].Len())
+ for _, col := range columns {
+ if int64(col.Len()) != length {
+ return nil, fmt.Errorf("%w: all columns must have the same length", arrow.ErrInvalid)
+ }
+ }
+
+ comparators := make([]columnComparator, len(columns))
Review Comment:
`len(keys)`?
##########
arrow/compute/internal/kernels/vector_sort.go:
##########
@@ -0,0 +1,476 @@
+// 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.
+
+//go:build go1.18
+
+package kernels
+
+import (
+ "fmt"
+ "slices"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/compute/exec"
+)
+
+// SortOrder specifies the sort order for sorting operations.
+type SortOrder int8
+
+const (
+ Ascending SortOrder = iota
+ Descending
+)
+
+// NullPlacement specifies where null values should be placed in the sort order.
+type NullPlacement int8
+
+const (
+ NullsAtEnd NullPlacement = iota
+ NullsAtStart
+)
+
+// SortOptions defines options for the sort_indices function.
+type SortOptions struct {
+ Order SortOrder `compute:"order"`
+ NullPlacement NullPlacement `compute:"null_placement"`
+}
+
+func (SortOptions) TypeName() string { return "SortOptions" }
+
+type SortState = SortOptions
+
+// SortKey defines a column to sort by with its ordering and null placement options.
+type SortKey struct {
+ ColumnIndex int
+ Order SortOrder
+ NullPlacement NullPlacement
+}
+
+// Chunk-aware sort_indices: logical row IDs 0..n-1, no chunk concatenation. Structure follows
+// Apache Arrow C++ vector_sort.cc / vector_sort_internal.h (see vector_sort_internal.go).
+//
+// Per-column data uses a dense logicalRowMap for O(1) chunk resolution under random compares.
+// Each sortable physical type has a dedicated comparator struct in vector_sort_physical.go (C++
+// ConcreteColumnComparator<T> shape): full monomorphization for the hot compare path; no
+// value-level compare func pointer.
+// compareRowsForKey implements the same ordering as C++ (null placement, NaN, Order).
+//
+// Single key: ChunkedArraySorter — arraySortOneColumnRange per chunk (PartitionNullsOnly /
+// PartitionNullLikes + stable_sort finites), then pairwise merge (ChunkedMergeImpl-style merge
+// using full row order; C++ splits null / non-null merge when the type has null-likes).
+//
+// Multi-key, aligned chunks: TableSorter — per-chunk RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter, then merge.
+//
+// Multi-key, single segment: RadixRecordBatchSorter (<= maxRadixSortKeys) or
+// MultipleKeyRecordBatchSorter (> maxRadixSortKeys).
+
+// maxRadixSortKeys matches Arrow C++ kMaxRadixSortKeys (vector_sort.cc): above this, one global
+// multi-key stable sort is used instead of MSD radix.
+const maxRadixSortKeys = 8
+
+// columnComparator is the Go analogue of compute::internal::ColumnComparator (vector_sort_internal.h):
+// per-column row compare + null / null-like metadata for partitioning.
+type columnComparator interface {
+ // compareRowsForKey returns -1 if i before j, +1 if i after j, 0 if tied on this column
+ // (both null, or both non-null and equal), so the caller may advance to the next sort key.
+ compareRowsForKey(i, j uint64, key SortKey) int
+ // isNullAt returns true if the global row index is null.
+ isNullAt(global uint64) bool
+ // hasNullLikeValues returns true if the column has null-like values.
+ hasNullLikeValues() bool
+ // isNullLikeAt returns true if the global row index is a null-like value.
+ isNullLikeAt(global uint64) bool
+ // columnHasValidityNulls mirrors Array::null_count() != 0; when false, C++ skips PartitionNullsOnly.
+ columnHasValidityNulls() bool
+}
+
+// multiColumnComparator compares two logical rows (global uint64 indices) lexicographically
+// across every sort key. That matches C++ MultipleKeyComparator::CompareInternal(left, right, 0)
+// (vector_sort_internal.h), but it is not a port of the whole MultipleKeyComparator type: C++ keeps
+// ResolvedSortKey per column, uses Location (int64 batch row vs ChunkLocation on tables), builds
+// virtual ColumnComparator instances, and passes start_sort_key_index for radix tails and other
+// partial key ranges — in Go those suffix compares are makeTailComparator(comparators, keys, from).
+type multiColumnComparator struct {
+ columns []columnComparator
+ keys []SortKey
+}
+
+// compare is a three-way ordering for stable sort / merge: negative if idxA before idxB, etc.
+func (m *multiColumnComparator) compare(idxA, idxB uint64) int {
+ for i, key := range m.keys {
+ if cmpVal := m.columns[i].compareRowsForKey(idxA, idxB, key); cmpVal != 0 {
+ return cmpVal
+ }
+ }
+ return 0
+}
+
+func extensionStorageFixedSizeBinaryChunks(chunks []arrow.Array) ([]arrow.Array, error) {
+ out := make([]arrow.Array, len(chunks))
+ for i, ch := range chunks {
+ ext, ok := ch.(array.ExtensionArray)
+ if !ok {
+ return nil, fmt.Errorf("%w: extension column must implement array.ExtensionArray", arrow.ErrInvalid)
+ }
+ st := ext.Storage()
+ if st.DataType().ID() != arrow.FIXED_SIZE_BINARY {
+ return nil, fmt.Errorf("%w: sorting extension columns is only supported when storage is fixed_size_binary (got %s)",
+ arrow.ErrNotImplemented, st.DataType())
+ }
+ out[i] = st
+ }
+ return out, nil
+}
+
+func newFixedSizeBinaryComparator(chunks []arrow.Array, numRows int, vn bool) (columnComparator, error) {
+ f0, ok := chunks[0].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ w := f0.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ for i := 1; i < len(chunks); i++ {
+ fi, ok := chunks[i].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ wi := fi.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ if wi != w {
+ return nil, fmt.Errorf("%w: fixed_size_binary chunks must have the same byte width (%d vs %d)",
+ arrow.ErrInvalid, w, wi)
+ }
+ }
+ return newPhysicalSortFixedSizeBinaryColumn(chunks, numRows, vn), nil
+}
+
+// createChunkedComparator builds a column comparator for these chunks (one Arrow type for all chunks).
+func createChunkedComparator(chunks []arrow.Array, numRows int) (columnComparator, error) {
+ if len(chunks) == 0 {
+ return nil, fmt.Errorf("%w: cannot create comparator for empty chunk list", arrow.ErrInvalid)
+ }
+ if totalChunkRows(chunks) != numRows {
+ return nil, fmt.Errorf("%w: chunk row count does not match column length", arrow.ErrInvalid)
+ }
+
+ validityNulls := chunksHaveNulls(chunks)
+ typeID := chunks[0].DataType().ID()
+ switch typeID {
+ case arrow.INT8:
+ return newPhysicalSortInt8Column(chunks, numRows, validityNulls), nil
+ case arrow.INT16:
+ return newPhysicalSortInt16Column(chunks, numRows, validityNulls), nil
+ case arrow.INT32:
+ return newPhysicalSortInt32Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE32:
+ return newPhysicalSortDate32Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME32:
+ return newPhysicalSortTime32Column(chunks, numRows, validityNulls), nil
+ case arrow.INT64:
+ return newPhysicalSortInt64Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE64:
+ return newPhysicalSortDate64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME64:
+ return newPhysicalSortTime64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIMESTAMP:
+ return newPhysicalSortTimestampColumn(chunks, numRows, validityNulls), nil
+ case arrow.DURATION:
+ return newPhysicalSortDurationColumn(chunks, numRows, validityNulls), nil
+ case arrow.UINT8:
+ return newPhysicalSortUint8Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT16:
+ return newPhysicalSortUint16Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT32:
+ return newPhysicalSortUint32Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT64:
+ return newPhysicalSortUint64Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT16:
+ return newPhysicalSortFloat16Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT32:
+ return newPhysicalSortFloat32Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT64:
+ return newPhysicalSortFloat64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL32:
+ return newPhysicalSortDecimal32Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL64:
+ return newPhysicalSortDecimal64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL128:
+ return newPhysicalSortDecimal128Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL256:
+ return newPhysicalSortDecimal256Column(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTHS:
+ return newPhysicalSortMonthIntervalColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_DAY_TIME:
+ return newPhysicalSortDayTimeColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTH_DAY_NANO:
+ return newPhysicalSortMonthDayNanoColumn(chunks, numRows, validityNulls), nil
+ case arrow.BOOL:
+ return newPhysicalSortBoolColumn(chunks, numRows, validityNulls), nil
+ case arrow.STRING:
+ return newPhysicalSortStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_STRING:
+ return newPhysicalSortLargeStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.BINARY:
+ return newPhysicalSortBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_BINARY:
+ return newPhysicalSortLargeBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.FIXED_SIZE_BINARY:
+ return newFixedSizeBinaryComparator(chunks, numRows, validityNulls)
+ case arrow.EXTENSION:
+ storageChunks, err := extensionStorageFixedSizeBinaryChunks(chunks)
+ if err != nil {
+ return nil, err
+ }
+ return newFixedSizeBinaryComparator(storageChunks, numRows, validityNulls)
+ default:
+ return nil, fmt.Errorf("%w: sorting not supported for type %s", arrow.ErrNotImplemented, typeID)
+ }
+}
+
+// chunkIndexSpan represents a contiguous range of indices in the global order.
+type chunkIndexSpan struct {
+ lo, hi int
+}
+
+// mergeAdjacentStable merges sorted adjacent ranges [a0,a1) and [b0,b1) (a1 == b0) into indices[lo:hi]
+// using a strict weak order: i is ordered before j iff less(i,j). Tie-breaking prefers the left range
+// (stable merge, same as C++ std::merge with !comp(right,left)).
+func mergeAdjacentStable(indices, tmp []uint64, a0, a1, b0, b1 int, less func(a, b uint64) bool) {
+ i, j, k := a0, b0, a0
+ for i < a1 && j < b1 {
+ if !less(indices[j], indices[i]) {
+ tmp[k] = indices[i]
+ i++
+ } else {
+ tmp[k] = indices[j]
+ j++
+ }
+ k++
+ }
+ for i < a1 {
+ tmp[k] = indices[i]
+ k++
+ i++
+ }
+ for j < b1 {
+ tmp[k] = indices[j]
+ k++
+ j++
+ }
+ copy(indices[a0:b1], tmp[a0:b1])
+}
+
+// pairwiseMergeSortedSpans merges already-sorted adjacent index spans (chunk batch rows in global
+// order), matching Arrow C++ ChunkedMergeImpl / TableSorter batch merge (vector_sort.cc).
+// spanScratch must have capacity >= len(spans); it ping-pongs with spans' backing during merging.
+func pairwiseMergeSortedSpans(indices, tmp []uint64, spans []chunkIndexSpan, less func(a, b uint64) bool, spanScratch []chunkIndexSpan) {
+ if len(spans) <= 1 {
+ return
+ }
+ if cap(spanScratch) < len(spans) {
+ panic("kernels: spanScratch cap < len(spans)")
+ }
+ cur := spans
+ other := spanScratch[:0]
+ for len(cur) > 1 {
+ other = other[:0]
+ for i := 0; i < len(cur); i += 2 {
+ if i+1 < len(cur) {
+ s0, s1 := cur[i], cur[i+1]
+ mergeAdjacentStable(indices, tmp, s0.lo, s0.hi, s1.lo, s1.hi, less)
+ other = append(other, chunkIndexSpan{s0.lo, s1.hi})
+ } else {
+ other = append(other, cur[i])
+ }
+ }
+ cur, other = other, cur
+ }
+}
+
+// alignedChunkBoundaries reports cumulative row offsets for chunk boundaries when every sort column
+// has the same chunk count and matching chunk lengths (typical for Arrow tables).
+func alignedChunkBoundaries(columns []*arrow.Chunked) ([]int, bool) {
+ if len(columns) == 0 {
+ return nil, false
+ }
+ ch0 := columns[0].Chunks()
+ n := len(ch0)
+ if n == 0 {
+ return nil, false
+ }
+ offs := make([]int, n+1)
+ for i := 0; i < n; i++ {
+ L := ch0[i].Len()
+ for j := 1; j < len(columns); j++ {
+ cj := columns[j].Chunks()
+ if len(cj) != n || cj[i].Len() != L {
+ return nil, false
+ }
+ }
+ offs[i+1] = offs[i] + L
+ }
+ if offs[n] != columns[0].Len() {
+ return nil, false
+ }
+ return offs, true
+}
+
+// sortIndicesSingleColumnChunked implements Arrow C++ ChunkedArraySorter for one logical column:
+// per-chunk array sort (partition + sort finites), then pairwise merge (ChunkedMergeImpl).
+func sortIndicesSingleColumnChunked(indices []uint64, chunks []arrow.Array, comp columnComparator, key SortKey, tmp []uint64, spanScratch []chunkIndexSpan) {
+ lo := 0
+ for _, ch := range chunks {
+ hi := lo + ch.Len()
+ arraySortOneColumnRange(indices, tmp, comp, key, lo, hi)
+ lo = hi
+ }
+
+ nChunks := len(chunks)
+ if nChunks <= 1 {
+ return
+ }
+
+ less := func(a, b uint64) bool { return comp.compareRowsForKey(a, b, key) < 0 }
+
+ spans := make([]chunkIndexSpan, nChunks)
+ lo = 0
+ for i, ch := range chunks {
+ hi := lo + ch.Len()
+ spans[i] = chunkIndexSpan{lo, hi}
+ lo = hi
+ }
+ pairwiseMergeSortedSpans(indices, tmp, spans, less, spanScratch)
+}
+
+// sortIndicesMultiColumnAlignedChunks sorts each aligned chunk (C++ RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter), then merges like Arrow C++ TableSorter.
+func sortIndicesMultiColumnAlignedChunks(indices []uint64, offs []int, comparators []columnComparator, keys []SortKey, multiComp *multiColumnComparator, tmp []uint64, spanScratch []chunkIndexSpan) {
+ nChunks := len(offs) - 1
+ useRadix := len(keys) <= maxRadixSortKeys
+ for c := 0; c < nChunks; c++ {
+ lo, hi := offs[c], offs[c+1]
+ if useRadix {
+ radixRecordBatchSortRange(indices, tmp, comparators, keys, 0, lo, hi)
+ } else {
+ multipleKeyRecordBatchSortRange(indices, tmp, comparators, keys, lo, hi, makeTailComparator(comparators, keys, 1))
+ }
+ }
+ if nChunks <= 1 {
+ return
+ }
+ less := func(a, b uint64) bool { return multiComp.compare(a, b) < 0 }
+ spans := make([]chunkIndexSpan, nChunks)
+ for c := 0; c < nChunks; c++ {
+ spans[c] = chunkIndexSpan{offs[c], offs[c+1]}
+ }
+ pairwiseMergeSortedSpans(indices, tmp, spans, less, spanScratch)
+}
+
+// SortIndices returns a stable permutation of 0..n-1 that would lexicographically sort the given
+// columns. Each *arrow.Chunked is used via its .Chunks() only—no concatenate. columns[i] pairs with
+// keys[i] for order and null placement on that column.
+func SortIndices(ctx *exec.KernelCtx, columns []*arrow.Chunked, keys []SortKey) (*exec.ExecResult, error) {
+ if len(columns) == 0 || len(keys) == 0 {
+ return nil, fmt.Errorf("%w: must have at least one column and one sort key", arrow.ErrInvalid)
+ }
+
+ if len(columns) != len(keys) {
+ return nil, fmt.Errorf("%w: number of columns (%d) must match number of sort keys (%d)",
+ arrow.ErrInvalid, len(columns), len(keys))
+ }
Review Comment:
why must it match the number of sort keys? Shouldn't it just be `len(columns) >= len(keys)`?
##########
arrow/compute/internal/kernels/vector_sort.go:
##########
@@ -0,0 +1,476 @@
+// 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.
+
+//go:build go1.18
+
+package kernels
+
+import (
+ "fmt"
+ "slices"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/compute/exec"
+)
+
+// SortOrder specifies the sort order for sorting operations.
+type SortOrder int8
+
+const (
+ Ascending SortOrder = iota
+ Descending
+)
+
+// NullPlacement specifies where null values should be placed in the sort order.
+type NullPlacement int8
+
+const (
+ NullsAtEnd NullPlacement = iota
+ NullsAtStart
+)
+
+// SortOptions defines options for the sort_indices function.
+type SortOptions struct {
+ Order SortOrder `compute:"order"`
+ NullPlacement NullPlacement `compute:"null_placement"`
+}
+
+func (SortOptions) TypeName() string { return "SortOptions" }
+
+type SortState = SortOptions
+
+// SortKey defines a column to sort by with its ordering and null placement options.
+type SortKey struct {
+ ColumnIndex int
+ Order SortOrder
+ NullPlacement NullPlacement
+}
+
+// Chunk-aware sort_indices: logical row IDs 0..n-1, no chunk concatenation. Structure follows
+// Apache Arrow C++ vector_sort.cc / vector_sort_internal.h (see vector_sort_internal.go).
+//
+// Per-column data uses a dense logicalRowMap for O(1) chunk resolution under random compares.
+// Each sortable physical type has a dedicated comparator struct in vector_sort_physical.go (C++
+// ConcreteColumnComparator<T> shape): full monomorphization for the hot compare path; no
+// value-level compare func pointer.
+// compareRowsForKey implements the same ordering as C++ (null placement, NaN, Order).
+//
+// Single key: ChunkedArraySorter — arraySortOneColumnRange per chunk (PartitionNullsOnly /
+// PartitionNullLikes + stable_sort finites), then pairwise merge (ChunkedMergeImpl-style merge
+// using full row order; C++ splits null / non-null merge when the type has null-likes).
+//
+// Multi-key, aligned chunks: TableSorter — per-chunk RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter, then merge.
+//
+// Multi-key, single segment: RadixRecordBatchSorter (<= maxRadixSortKeys) or
+// MultipleKeyRecordBatchSorter (> maxRadixSortKeys).
+
+// maxRadixSortKeys matches Arrow C++ kMaxRadixSortKeys (vector_sort.cc): above this, one global
+// multi-key stable sort is used instead of MSD radix.
+const maxRadixSortKeys = 8
+
+// columnComparator is the Go analogue of compute::internal::ColumnComparator (vector_sort_internal.h):
+// per-column row compare + null / null-like metadata for partitioning.
+type columnComparator interface {
+ // compareRowsForKey returns -1 if i before j, +1 if i after j, 0 if tied on this column
+ // (both null, or both non-null and equal), so the caller may advance to the next sort key.
+ compareRowsForKey(i, j uint64, key SortKey) int
+ // isNullAt returns true if the global row index is null.
+ isNullAt(global uint64) bool
+ // hasNullLikeValues returns true if the column has null-like values.
+ hasNullLikeValues() bool
+ // isNullLikeAt returns true if the global row index is a null-like value.
+ isNullLikeAt(global uint64) bool
+ // columnHasValidityNulls mirrors Array::null_count() != 0; when false, C++ skips PartitionNullsOnly.
+ columnHasValidityNulls() bool
+}
+
+// multiColumnComparator compares two logical rows (global uint64 indices) lexicographically
+// across every sort key. That matches C++ MultipleKeyComparator::CompareInternal(left, right, 0)
+// (vector_sort_internal.h), but it is not a port of the whole MultipleKeyComparator type: C++ keeps
+// ResolvedSortKey per column, uses Location (int64 batch row vs ChunkLocation on tables), builds
+// virtual ColumnComparator instances, and passes start_sort_key_index for radix tails and other
+// partial key ranges — in Go those suffix compares are makeTailComparator(comparators, keys, from).
+type multiColumnComparator struct {
+ columns []columnComparator
+ keys []SortKey
+}
+
+// compare is a three-way ordering for stable sort / merge: negative if idxA before idxB, etc.
+func (m *multiColumnComparator) compare(idxA, idxB uint64) int {
+ for i, key := range m.keys {
+ if cmpVal := m.columns[i].compareRowsForKey(idxA, idxB, key); cmpVal != 0 {
+ return cmpVal
+ }
+ }
+ return 0
+}
+
+func extensionStorageFixedSizeBinaryChunks(chunks []arrow.Array) ([]arrow.Array, error) {
+ out := make([]arrow.Array, len(chunks))
+ for i, ch := range chunks {
+ ext, ok := ch.(array.ExtensionArray)
+ if !ok {
+ return nil, fmt.Errorf("%w: extension column must implement array.ExtensionArray", arrow.ErrInvalid)
+ }
+ st := ext.Storage()
+ if st.DataType().ID() != arrow.FIXED_SIZE_BINARY {
+ return nil, fmt.Errorf("%w: sorting extension columns is only supported when storage is fixed_size_binary (got %s)",
+ arrow.ErrNotImplemented, st.DataType())
+ }
+ out[i] = st
+ }
+ return out, nil
+}
+
+func newFixedSizeBinaryComparator(chunks []arrow.Array, numRows int, vn bool) (columnComparator, error) {
+ f0, ok := chunks[0].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ w := f0.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ for i := 1; i < len(chunks); i++ {
+ fi, ok := chunks[i].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ wi := fi.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ if wi != w {
+ return nil, fmt.Errorf("%w: fixed_size_binary chunks must have the same byte width (%d vs %d)",
+ arrow.ErrInvalid, w, wi)
+ }
+ }
+ return newPhysicalSortFixedSizeBinaryColumn(chunks, numRows, vn), nil
+}
+
+// createChunkedComparator builds a column comparator for these chunks (one Arrow type for all chunks).
+func createChunkedComparator(chunks []arrow.Array, numRows int) (columnComparator, error) {
+ if len(chunks) == 0 {
+ return nil, fmt.Errorf("%w: cannot create comparator for empty chunk list", arrow.ErrInvalid)
+ }
+ if totalChunkRows(chunks) != numRows {
+ return nil, fmt.Errorf("%w: chunk row count does not match column length", arrow.ErrInvalid)
+ }
+
+ validityNulls := chunksHaveNulls(chunks)
+ typeID := chunks[0].DataType().ID()
+ switch typeID {
+ case arrow.INT8:
+ return newPhysicalSortInt8Column(chunks, numRows, validityNulls), nil
+ case arrow.INT16:
+ return newPhysicalSortInt16Column(chunks, numRows, validityNulls), nil
+ case arrow.INT32:
+ return newPhysicalSortInt32Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE32:
+ return newPhysicalSortDate32Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME32:
+ return newPhysicalSortTime32Column(chunks, numRows, validityNulls), nil
+ case arrow.INT64:
+ return newPhysicalSortInt64Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE64:
+ return newPhysicalSortDate64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME64:
+ return newPhysicalSortTime64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIMESTAMP:
+ return newPhysicalSortTimestampColumn(chunks, numRows, validityNulls), nil
+ case arrow.DURATION:
+ return newPhysicalSortDurationColumn(chunks, numRows, validityNulls), nil
+ case arrow.UINT8:
+ return newPhysicalSortUint8Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT16:
+ return newPhysicalSortUint16Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT32:
+ return newPhysicalSortUint32Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT64:
+ return newPhysicalSortUint64Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT16:
+ return newPhysicalSortFloat16Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT32:
+ return newPhysicalSortFloat32Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT64:
+ return newPhysicalSortFloat64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL32:
+ return newPhysicalSortDecimal32Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL64:
+ return newPhysicalSortDecimal64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL128:
+ return newPhysicalSortDecimal128Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL256:
+ return newPhysicalSortDecimal256Column(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTHS:
+ return newPhysicalSortMonthIntervalColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_DAY_TIME:
+ return newPhysicalSortDayTimeColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTH_DAY_NANO:
+ return newPhysicalSortMonthDayNanoColumn(chunks, numRows, validityNulls), nil
+ case arrow.BOOL:
+ return newPhysicalSortBoolColumn(chunks, numRows, validityNulls), nil
+ case arrow.STRING:
+ return newPhysicalSortStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_STRING:
+ return newPhysicalSortLargeStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.BINARY:
+ return newPhysicalSortBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_BINARY:
+ return newPhysicalSortLargeBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.FIXED_SIZE_BINARY:
+ return newFixedSizeBinaryComparator(chunks, numRows, validityNulls)
+ case arrow.EXTENSION:
+ storageChunks, err := extensionStorageFixedSizeBinaryChunks(chunks)
+ if err != nil {
+ return nil, err
+ }
+ return newFixedSizeBinaryComparator(storageChunks, numRows, validityNulls)
+ default:
+ return nil, fmt.Errorf("%w: sorting not supported for type %s", arrow.ErrNotImplemented, typeID)
+ }
+}
+
+// chunkIndexSpan represents a contiguous range of indices in the global order.
+type chunkIndexSpan struct {
+ lo, hi int
+}
+
+// mergeAdjacentStable merges sorted adjacent ranges [a0,a1) and [b0,b1) (a1 == b0) into indices[lo:hi]
+// using a strict weak order: i is ordered before j iff less(i,j). Tie-breaking prefers the left range
+// (stable merge, same as C++ std::merge with !comp(right,left)).
+func mergeAdjacentStable(indices, tmp []uint64, a0, a1, b0, b1 int, less func(a, b uint64) bool) {
+ i, j, k := a0, b0, a0
+ for i < a1 && j < b1 {
+ if !less(indices[j], indices[i]) {
+ tmp[k] = indices[i]
+ i++
+ } else {
+ tmp[k] = indices[j]
+ j++
+ }
+ k++
+ }
+ for i < a1 {
+ tmp[k] = indices[i]
+ k++
+ i++
+ }
+ for j < b1 {
+ tmp[k] = indices[j]
+ k++
+ j++
+ }
+ copy(indices[a0:b1], tmp[a0:b1])
+}
+
+// pairwiseMergeSortedSpans merges already-sorted adjacent index spans (chunk batch rows in global
+// order), matching Arrow C++ ChunkedMergeImpl / TableSorter batch merge (vector_sort.cc).
+// spanScratch must have capacity >= len(spans); it ping-pongs with spans' backing during merging.
+func pairwiseMergeSortedSpans(indices, tmp []uint64, spans []chunkIndexSpan, less func(a, b uint64) bool, spanScratch []chunkIndexSpan) {
+ if len(spans) <= 1 {
+ return
+ }
+ if cap(spanScratch) < len(spans) {
+ panic("kernels: spanScratch cap < len(spans)")
+ }
+ cur := spans
+ other := spanScratch[:0]
+ for len(cur) > 1 {
+ other = other[:0]
+ for i := 0; i < len(cur); i += 2 {
+ if i+1 < len(cur) {
+ s0, s1 := cur[i], cur[i+1]
+ mergeAdjacentStable(indices, tmp, s0.lo, s0.hi, s1.lo, s1.hi, less)
+ other = append(other, chunkIndexSpan{s0.lo, s1.hi})
+ } else {
+ other = append(other, cur[i])
+ }
+ }
+ cur, other = other, cur
+ }
+}
+
+// alignedChunkBoundaries reports cumulative row offsets for chunk boundaries when every sort column
+// has the same chunk count and matching chunk lengths (typical for Arrow tables).
+func alignedChunkBoundaries(columns []*arrow.Chunked) ([]int, bool) {
+ if len(columns) == 0 {
+ return nil, false
+ }
+ ch0 := columns[0].Chunks()
+ n := len(ch0)
+ if n == 0 {
+ return nil, false
+ }
+ offs := make([]int, n+1)
+ for i := 0; i < n; i++ {
+ L := ch0[i].Len()
+ for j := 1; j < len(columns); j++ {
+ cj := columns[j].Chunks()
+ if len(cj) != n || cj[i].Len() != L {
+ return nil, false
+ }
+ }
+ offs[i+1] = offs[i] + L
+ }
+ if offs[n] != columns[0].Len() {
+ return nil, false
+ }
+ return offs, true
+}
+
+// sortIndicesSingleColumnChunked implements Arrow C++ ChunkedArraySorter for one logical column:
+// per-chunk array sort (partition + sort finites), then pairwise merge (ChunkedMergeImpl).
+func sortIndicesSingleColumnChunked(indices []uint64, chunks []arrow.Array, comp columnComparator, key SortKey, tmp []uint64, spanScratch []chunkIndexSpan) {
+ lo := 0
+ for _, ch := range chunks {
+ hi := lo + ch.Len()
+ arraySortOneColumnRange(indices, tmp, comp, key, lo, hi)
+ lo = hi
+ }
+
+ nChunks := len(chunks)
+ if nChunks <= 1 {
+ return
+ }
+
+ less := func(a, b uint64) bool { return comp.compareRowsForKey(a, b, key) < 0 }
+
+ spans := make([]chunkIndexSpan, nChunks)
+ lo = 0
+ for i, ch := range chunks {
+ hi := lo + ch.Len()
+ spans[i] = chunkIndexSpan{lo, hi}
+ lo = hi
+ }
+ pairwiseMergeSortedSpans(indices, tmp, spans, less, spanScratch)
+}
+
+// sortIndicesMultiColumnAlignedChunks sorts each aligned chunk (C++ RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter), then merges like Arrow C++ TableSorter.
+func sortIndicesMultiColumnAlignedChunks(indices []uint64, offs []int, comparators []columnComparator, keys []SortKey, multiComp *multiColumnComparator, tmp []uint64, spanScratch []chunkIndexSpan) {
+ nChunks := len(offs) - 1
+ useRadix := len(keys) <= maxRadixSortKeys
+ for c := 0; c < nChunks; c++ {
+ lo, hi := offs[c], offs[c+1]
+ if useRadix {
+ radixRecordBatchSortRange(indices, tmp, comparators, keys, 0, lo, hi)
+ } else {
+ multipleKeyRecordBatchSortRange(indices, tmp, comparators, keys, lo, hi, makeTailComparator(comparators, keys, 1))
+ }
+ }
+ if nChunks <= 1 {
+ return
+ }
+ less := func(a, b uint64) bool { return multiComp.compare(a, b) < 0 }
+ spans := make([]chunkIndexSpan, nChunks)
+ for c := 0; c < nChunks; c++ {
+ spans[c] = chunkIndexSpan{offs[c], offs[c+1]}
+ }
+ pairwiseMergeSortedSpans(indices, tmp, spans, less, spanScratch)
+}
+
+// SortIndices returns a stable permutation of 0..n-1 that would lexicographically sort the given
+// columns. Each *arrow.Chunked is used via its .Chunks() only—no concatenate. columns[i] pairs with
+// keys[i] for order and null placement on that column.
+func SortIndices(ctx *exec.KernelCtx, columns []*arrow.Chunked, keys []SortKey) (*exec.ExecResult, error) {
+ if len(columns) == 0 || len(keys) == 0 {
+ return nil, fmt.Errorf("%w: must have at least one column and one sort key", arrow.ErrInvalid)
+ }
+
+ if len(columns) != len(keys) {
+ return nil, fmt.Errorf("%w: number of columns (%d) must match number of sort keys (%d)",
+ arrow.ErrInvalid, len(columns), len(keys))
+ }
+
+ length := int64(columns[0].Len())
+ for _, col := range columns {
+ if int64(col.Len()) != length {
+ return nil, fmt.Errorf("%w: all columns must have the same length", arrow.ErrInvalid)
+ }
+ }
+
+ comparators := make([]columnComparator, len(columns))
+ nRows := int(length)
+ for i, col := range columns {
+ comp, err := createChunkedComparator(col.Chunks(), nRows)
+ if err != nil {
+ return nil, err
+ }
+ comparators[i] = comp
+ }
+
+ multiComp := &multiColumnComparator{
+ columns: comparators,
+ keys: keys,
+ }
+
+ out := &exec.ExecResult{}
+ out.Len = length
+ out.Type = arrow.PrimitiveTypes.Uint64
+ out.Nulls = 0
+
+ buf := ctx.Allocate(int(length) * arrow.Uint64SizeBytes)
+ indices := arrow.Uint64Traits.CastFromBytes(buf.Buf())[:length]
+
+ for i := range indices {
+ indices[i] = uint64(i)
+ }
+
+ if len(keys) == 1 {
+ chunks := columns[0].Chunks()
+ if len(chunks) > 1 {
+ tmpBuf := ctx.Allocate(nRows * arrow.Uint64SizeBytes)
+ tmp := arrow.Uint64Traits.CastFromBytes(tmpBuf.Buf())[:nRows]
Review Comment:
same as above, use `arrow.GetData[uint64](tmpBuf.Buf())[:nRows]`
##########
arrow/compute/internal/kernels/vector_sort_internal.go:
##########
@@ -0,0 +1,280 @@
+// 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.
+
+//go:build go1.18
+
+package kernels
+
+import (
+ "slices"
+)
+
+// Ported from Apache Arrow C++ vector_sort_internal.h / vector_sort.cc:
+// GenericNullPartitionResult, PartitionNullsOnly, PartitionNullLikes, VisitConstantRanges,
+// ConcreteRecordBatchColumnSorter::SortRange (radix / column-wise multi-key path).
+
+// nullPartitionIndices holds inclusive-exclusive offsets into the indices buffer (like uint64_t*
+// ranges in C++ GenericNullPartitionResult).
+type nullPartitionIndices struct {
+ nonNullsLo, nonNullsHi int
+ nullsLo, nullsHi int
+}
+
+// partitionNullsOnly mirrors PartitionNullsOnly<StablePartitioner> in vector_sort_internal.h.
+func partitionNullsOnly(indices, scratch []uint64, lo, hi int, nullPlacement NullPlacement, isNull func(uint64) bool) nullPartitionIndices {
+ if lo >= hi {
+ return nullPartitionIndices{lo, lo, lo, lo}
+ }
+ hasNull := false
+ for i := lo; i < hi; i++ {
+ if isNull(indices[i]) {
+ hasNull = true
+ break
+ }
+ }
+ if !hasNull {
+ if nullPlacement == NullsAtStart {
+ return nullPartitionIndices{lo, hi, lo, lo}
+ }
+ return nullPartitionIndices{lo, hi, hi, hi}
+ }
+ if nullPlacement == NullsAtStart {
+ t := 0
+ for i := lo; i < hi; i++ {
+ if isNull(indices[i]) {
+ scratch[lo+t] = indices[i]
+ t++
+ }
+ }
+ nullEnd := lo + t
+ u := t
+ for i := lo; i < hi; i++ {
+ if !isNull(indices[i]) {
+ scratch[lo+u] = indices[i]
+ u++
+ }
+ }
+ copy(indices[lo:hi], scratch[lo:hi])
+ return nullPartitionIndices{nullEnd, hi, lo, nullEnd}
+ }
+ t := 0
+ for i := lo; i < hi; i++ {
+ if !isNull(indices[i]) {
+ scratch[lo+t] = indices[i]
+ t++
+ }
+ }
+ nnEnd := lo + t
+ u := t
+ for i := lo; i < hi; i++ {
+ if isNull(indices[i]) {
+ scratch[lo+u] = indices[i]
+ u++
+ }
+ }
+ copy(indices[lo:hi], scratch[lo:hi])
+ return nullPartitionIndices{lo, nnEnd, nnEnd, hi}
+}
+
+// partitionNullLikes mirrors PartitionNullLikes in vector_sort_internal.h (NaN for floats).
+func partitionNullLikes(indices, scratch []uint64, lo, hi int, nullPlacement NullPlacement, hasNullLike bool, isNullLike func(uint64) bool) nullPartitionIndices {
+ if !hasNullLike || lo >= hi {
+ if nullPlacement == NullsAtStart {
+ return nullPartitionIndices{lo, hi, lo, lo}
+ }
+ return nullPartitionIndices{lo, hi, hi, hi}
+ }
+ hasLike := false
+ for i := lo; i < hi; i++ {
+ if isNullLike(indices[i]) {
+ hasLike = true
+ break
+ }
+ }
+ if !hasLike {
+ if nullPlacement == NullsAtStart {
+ return nullPartitionIndices{lo, hi, lo, lo}
+ }
+ return nullPartitionIndices{lo, hi, hi, hi}
+ }
+ if nullPlacement == NullsAtStart {
+ t := 0
+ for i := lo; i < hi; i++ {
+ if isNullLike(indices[i]) {
+ scratch[lo+t] = indices[i]
+ t++
+ }
+ }
+ likeEnd := lo + t
+ u := t
+ for i := lo; i < hi; i++ {
+ if !isNullLike(indices[i]) {
+ scratch[lo+u] = indices[i]
+ u++
+ }
+ }
+ copy(indices[lo:hi], scratch[lo:hi])
+ return nullPartitionIndices{likeEnd, hi, lo, likeEnd}
+ }
+ t := 0
+ for i := lo; i < hi; i++ {
+ if !isNullLike(indices[i]) {
+ scratch[lo+t] = indices[i]
+ t++
+ }
+ }
+ finEnd := lo + t
+ u := t
+ for i := lo; i < hi; i++ {
+ if isNullLike(indices[i]) {
+ scratch[lo+u] = indices[i]
+ u++
+ }
+ }
+ copy(indices[lo:hi], scratch[lo:hi])
+ return nullPartitionIndices{lo, finEnd, finEnd, hi}
+}
+
+// nullPartitionNoValidityNulls is PartitionNullsOnly when null_count == 0 (vector_sort_internal.h).
+func nullPartitionNoValidityNulls(lo, hi int, nullPlacement NullPlacement) nullPartitionIndices {
+ if nullPlacement == NullsAtStart {
+ return nullPartitionIndices{lo, hi, lo, lo}
+ }
+ return nullPartitionIndices{lo, hi, hi, hi}
+}
+
+// visitConstantRanges mirrors VisitConstantRanges in vector_sort.cc.
+func visitConstantRanges(indices []uint64, offsetLo, offsetHi int, key SortKey, comp columnComparator, visit func(rs, re int)) {
Review Comment:
couldn't we simplify this by just passing `indices[offsetLo:offsetHi]` into this instead of having to do all the complex logic below?
##########
arrow/compute/vector_sort.go:
##########
@@ -0,0 +1,391 @@
+// 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.
+
+//go:build go1.18
+
+package compute
+
+import (
+ "context"
+ "fmt"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/compute/exec"
+ "github.com/apache/arrow-go/v18/arrow/compute/internal/kernels"
+)
+
+var (
+ sortIndicesDoc = FunctionDoc{
+ Summary: "Return the indices that would sort the input",
+ Description: `This function computes an array of indices that define a stable sort.
+Supports arrays, chunked arrays, record batches, and tables.
+For arrays and chunked arrays, use a single SortKey (ColumnIndex is ignored).
+For record batches and tables, use []SortKey to specify columns and sort
+order; at least one key is required. Each key must reference a valid column.`,
+ ArgNames: []string{"input"},
+ OptionsType: "SortKeys",
+ }
+
+ sortIndicesMetaFunc = NewMetaFunction("sort_indices", Unary(), sortIndicesDoc,
+ func(ctx context.Context, opts FunctionOptions, args ...Datum) (Datum, error) {
+ input := args[0]
+ switch input.Kind() {
+ case KindArray, KindChunked, KindRecord, KindTable:
+ return sortIndicesImpl(ctx, opts, input)
+ }
+
+ return nil, fmt.Errorf("%w: unsupported type for sort_indices operation: %s",
+ arrow.ErrNotImplemented, input)
+ })
+
+ sortDoc = FunctionDoc{
+ Summary: "Return a sorted copy of the input",
+ Description: `This function sorts the input using the same ordering as sort_indices
+and returns the reordered values. It is equivalent to take(input,
+sort_indices(input, options)).
+Supports arrays, chunked arrays, record batches, and tables with the same
+SortKeys options as sort_indices.`,
+ ArgNames: []string{"input"},
+ OptionsType: "SortKeys",
+ }
+
+ sortMetaFunc = NewMetaFunction("sort", Unary(), sortDoc,
+ func(ctx context.Context, opts FunctionOptions, args ...Datum) (Datum, error) {
+ input := args[0]
+ switch input.Kind() {
+ case KindArray, KindChunked, KindRecord, KindTable:
+ default:
+ return nil, fmt.Errorf("%w: unsupported type for sort: %s", arrow.ErrNotImplemented, input)
+ }
+
+ indices, err := CallFunction(ctx, "sort_indices", opts, input)
+ if err != nil {
+ return nil, err
+ }
+ defer indices.Release()
+
+ return Take(ctx, *DefaultTakeOptions(), input, indices)
+ })
+)
+
+const (
+ SortOrderAscending = kernels.Ascending
+ SortOrderDescending = kernels.Descending
+ SortNullsAtEnd = kernels.NullsAtEnd
+ SortNullsAtStart = kernels.NullsAtStart
+)
+
+// SortKey defines a column to sort by with its ordering and null placement options.
+type SortKey = kernels.SortKey
+
+// SortOptions defines the desired sort order for the input.
+type SortOptions []SortKey
+
+// TypeName implements FunctionOptions.
+func (SortOptions) TypeName() string { return "SortKeys" }
+
+// DefaultSortKey returns the default sort key: ascending order with nulls last.
+func DefaultSortKey() SortKey {
+ return SortKey{
+ ColumnIndex: 0,
+ Order: kernels.Ascending,
+ NullPlacement: kernels.NullsAtEnd,
+ }
+}
+
+// sortIndicesImpl adapts any supported Datum to kernels.SortIndices (internal/kernels), which
+// implements a stable lexicographic sort over []*arrow.Chunked (one logical column per sort key,
+// same row count).
+//
+// Only the columns referenced by sort keys are passed to the kernel; the rest of the batch/table
+// is irrelevant to index computation. Chunked wrappers we allocate with arrow.NewChunked must be
+// released in the defer below (needsRelease); table column *arrow.Chunked values are borrowed from
+// the table and must not be released here.
+func sortIndicesImpl(ctx context.Context, opts FunctionOptions, input Datum) (Datum, error) {
+ inputSortKeys := opts.(SortOptions)
+ if len(inputSortKeys) == 0 {
+ return nil, fmt.Errorf("%w: must provide at least one sort key", arrow.ErrInvalid)
+ }
+
+ var sortColumns []*arrow.Chunked
+ // For KindRecord/KindTable, sortKeys stays aligned with inputSortKeys (multi-column sort).
+ // For KindArray/KindChunked, sortKeys is replaced with a single key (see those cases).
+ sortKeys := []kernels.SortKey(inputSortKeys)
+ var needsRelease []bool
+
+ switch input.Kind() {
+ case KindArray:
+ // Single column: one Array wrapped as a one-chunk Chunked (kernel API).
+ arr := input.(*ArrayDatum).MakeArray()
+ defer arr.Release()
+ chunked := arrow.NewChunked(arr.DataType(), []arrow.Array{arr})
+ sortColumns = []*arrow.Chunked{chunked}
+ needsRelease = []bool{true}
+
+ // Only the first key is used; ColumnIndex is meaningless for a bare array—copy the key and
+ // set index 0 so the kernel sees a consistent (column, key) pair (order/null placement preserved).
+ key := inputSortKeys[0]
+ key.ColumnIndex = 0
+ sortKeys = []kernels.SortKey{key}
+
+ case KindChunked:
+ // Single column: use the Chunked as-is (caller-owned; do not Release).
+ chunked := input.(*ChunkedDatum).Value
+ sortColumns = []*arrow.Chunked{chunked}
+ needsRelease = []bool{false}
+
+ key := inputSortKeys[0]
+ key.ColumnIndex = 0
+ sortKeys = []kernels.SortKey{key}
+
+ case KindRecord:
+ batch := input.(*RecordDatum).Value
+
+ sortColumns = make([]*arrow.Chunked, len(inputSortKeys))
+ needsRelease = make([]bool, len(inputSortKeys))
+ for i, key := range inputSortKeys {
+ if key.ColumnIndex < 0 || int64(key.ColumnIndex) >= batch.NumCols() {
+ return nil, fmt.Errorf("%w: sort key %d has invalid column index %d", arrow.ErrInvalid, i, key.ColumnIndex)
+ }
+ col := batch.Column(key.ColumnIndex)
+ // One batch column as a single-chunk Chunked per key; we own these Chunked values.
+ sortColumns[i] = arrow.NewChunked(col.DataType(), []arrow.Array{col})
+ needsRelease[i] = true
+ }
+
+ case KindTable:
+ tbl := input.(*TableDatum).Value
+
+ sortColumns = make([]*arrow.Chunked, len(inputSortKeys))
+ needsRelease = make([]bool, len(inputSortKeys))
+ for i, key := range inputSortKeys {
+ if key.ColumnIndex < 0 || int64(key.ColumnIndex) >= tbl.NumCols() {
+ return nil, fmt.Errorf("%w: sort key %d has invalid column index %d", arrow.ErrInvalid, i, key.ColumnIndex)
+ }
+ // Table columns are already Chunked; borrow from the table (do not Release).
+ sortColumns[i] = tbl.Column(key.ColumnIndex).Data()
+ needsRelease[i] = false
+ }
+
+ default:
+ return nil, fmt.Errorf("%w: unsupported type for sort_indices operation: %s", arrow.ErrNotImplemented, input)
+ }
+
+ defer func() {
+ for i, shouldRelease := range needsRelease {
+ if shouldRelease {
+ sortColumns[i].Release()
+ }
+ }
+ }()
+
+ allocator := exec.GetAllocator(ctx)
+ // Kernel expects exec allocator on context; avoid canceling user ctx mid-sort.
+ execCtx := &exec.KernelCtx{Ctx: exec.WithAllocator(context.Background(), allocator)}
Review Comment:
i'm confused, why would we cancel the user ctx mid-sort? Doing this means that if the input ctx gets cancelled on us, we won't honor it and cancel the operation. That's a problem
##########
arrow/compute/vector_sort.go:
##########
@@ -0,0 +1,391 @@
+// 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.
+
+//go:build go1.18
+
+package compute
+
+import (
+ "context"
+ "fmt"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/compute/exec"
+ "github.com/apache/arrow-go/v18/arrow/compute/internal/kernels"
+)
+
+var (
+ sortIndicesDoc = FunctionDoc{
+ Summary: "Return the indices that would sort the input",
+ Description: `This function computes an array of indices that define a stable sort.
+Supports arrays, chunked arrays, record batches, and tables.
+For arrays and chunked arrays, use a single SortKey (ColumnIndex is ignored).
+For record batches and tables, use []SortKey to specify columns and sort
+order; at least one key is required. Each key must reference a valid column.`,
+ ArgNames: []string{"input"},
+ OptionsType: "SortKeys",
+ }
+
+ sortIndicesMetaFunc = NewMetaFunction("sort_indices", Unary(), sortIndicesDoc,
+ func(ctx context.Context, opts FunctionOptions, args ...Datum) (Datum, error) {
+ input := args[0]
+ switch input.Kind() {
+ case KindArray, KindChunked, KindRecord, KindTable:
+ return sortIndicesImpl(ctx, opts, input)
+ }
+
+ return nil, fmt.Errorf("%w: unsupported type for sort_indices operation: %s",
+ arrow.ErrNotImplemented, input)
+ })
+
+ sortDoc = FunctionDoc{
+ Summary: "Return a sorted copy of the input",
+ Description: `This function sorts the input using the same ordering as sort_indices
+and returns the reordered values. It is equivalent to take(input,
+sort_indices(input, options)).
+Supports arrays, chunked arrays, record batches, and tables with the same
+SortKeys options as sort_indices.`,
+ ArgNames: []string{"input"},
+ OptionsType: "SortKeys",
+ }
+
+ sortMetaFunc = NewMetaFunction("sort", Unary(), sortDoc,
+ func(ctx context.Context, opts FunctionOptions, args ...Datum) (Datum, error) {
+ input := args[0]
+ switch input.Kind() {
+ case KindArray, KindChunked, KindRecord, KindTable:
+ default:
+ return nil, fmt.Errorf("%w: unsupported type for sort: %s", arrow.ErrNotImplemented, input)
+ }
+
+ indices, err := CallFunction(ctx, "sort_indices", opts, input)
+ if err != nil {
+ return nil, err
+ }
+ defer indices.Release()
+
+ return Take(ctx, *DefaultTakeOptions(), input, indices)
+ })
+)
+
+const (
+ SortOrderAscending = kernels.Ascending
+ SortOrderDescending = kernels.Descending
+ SortNullsAtEnd = kernels.NullsAtEnd
+ SortNullsAtStart = kernels.NullsAtStart
+)
+
+// SortKey defines a column to sort by with its ordering and null placement options.
+type SortKey = kernels.SortKey
+
+// SortOptions defines the desired sort order for the input.
+type SortOptions []SortKey
+
+// TypeName implements FunctionOptions.
+func (SortOptions) TypeName() string { return "SortKeys" }
+
+// DefaultSortKey returns the default sort key: ascending order with nulls last.
+func DefaultSortKey() SortKey {
+ return SortKey{
+ ColumnIndex: 0,
+ Order: kernels.Ascending,
+ NullPlacement: kernels.NullsAtEnd,
+ }
+}
+
+// sortIndicesImpl adapts any supported Datum to kernels.SortIndices (internal/kernels), which
+// implements a stable lexicographic sort over []*arrow.Chunked (one logical column per sort key,
+// same row count).
+//
+// Only the columns referenced by sort keys are passed to the kernel; the rest of the batch/table
+// is irrelevant to index computation. Chunked wrappers we allocate with arrow.NewChunked must be
+// released in the defer below (needsRelease); table column *arrow.Chunked values are borrowed from
+// the table and must not be released here.
+func sortIndicesImpl(ctx context.Context, opts FunctionOptions, input Datum) (Datum, error) {
+ inputSortKeys := opts.(SortOptions)
+ if len(inputSortKeys) == 0 {
+ return nil, fmt.Errorf("%w: must provide at least one sort key", arrow.ErrInvalid)
+ }
+
+ var sortColumns []*arrow.Chunked
+ // For KindRecord/KindTable, sortKeys stays aligned with inputSortKeys (multi-column sort).
+ // For KindArray/KindChunked, sortKeys is replaced with a single key (see those cases).
+ sortKeys := []kernels.SortKey(inputSortKeys)
+ var needsRelease []bool
+
+ switch input.Kind() {
+ case KindArray:
+ // Single column: one Array wrapped as a one-chunk Chunked (kernel API).
+ arr := input.(*ArrayDatum).MakeArray()
+ defer arr.Release()
+ chunked := arrow.NewChunked(arr.DataType(), []arrow.Array{arr})
+ sortColumns = []*arrow.Chunked{chunked}
+ needsRelease = []bool{true}
+
+ // Only the first key is used; ColumnIndex is meaningless for a bare array—copy the key and
+ // set index 0 so the kernel sees a consistent (column, key) pair (order/null placement preserved).
+ key := inputSortKeys[0]
+ key.ColumnIndex = 0
+ sortKeys = []kernels.SortKey{key}
+
+ case KindChunked:
+ // Single column: use the Chunked as-is (caller-owned; do not Release).
+ chunked := input.(*ChunkedDatum).Value
+ sortColumns = []*arrow.Chunked{chunked}
+ needsRelease = []bool{false}
+
+ key := inputSortKeys[0]
+ key.ColumnIndex = 0
+ sortKeys = []kernels.SortKey{key}
+
+ case KindRecord:
+ batch := input.(*RecordDatum).Value
+
+ sortColumns = make([]*arrow.Chunked, len(inputSortKeys))
+ needsRelease = make([]bool, len(inputSortKeys))
+ for i, key := range inputSortKeys {
Review Comment:
if we're pre-ordering by the sort keys ColumnIndex fields, we should at least document that in the internal kernel implementation that this is assumed to have happened already.
##########
arrow/compute/internal/kernels/vector_sort.go:
##########
@@ -0,0 +1,476 @@
+// 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.
+
+//go:build go1.18
+
+package kernels
+
+import (
+ "fmt"
+ "slices"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/compute/exec"
+)
+
+// SortOrder specifies the sort order for sorting operations.
+type SortOrder int8
+
+const (
+ Ascending SortOrder = iota
+ Descending
+)
+
+// NullPlacement specifies where null values should be placed in the sort order.
+type NullPlacement int8
+
+const (
+ NullsAtEnd NullPlacement = iota
+ NullsAtStart
+)
+
+// SortOptions defines options for the sort_indices function.
+type SortOptions struct {
+ Order SortOrder `compute:"order"`
+ NullPlacement NullPlacement `compute:"null_placement"`
+}
+
+func (SortOptions) TypeName() string { return "SortOptions" }
+
+type SortState = SortOptions
+
+// SortKey defines a column to sort by with its ordering and null placement options.
+type SortKey struct {
+ ColumnIndex int
+ Order SortOrder
+ NullPlacement NullPlacement
+}
+
+// Chunk-aware sort_indices: logical row IDs 0..n-1, no chunk concatenation. Structure follows
+// Apache Arrow C++ vector_sort.cc / vector_sort_internal.h (see vector_sort_internal.go).
+//
+// Per-column data uses a dense logicalRowMap for O(1) chunk resolution under random compares.
+// Each sortable physical type has a dedicated comparator struct in vector_sort_physical.go (C++
+// ConcreteColumnComparator<T> shape): full monomorphization for the hot compare path; no
+// value-level compare func pointer.
+// compareRowsForKey implements the same ordering as C++ (null placement, NaN, Order).
+//
+// Single key: ChunkedArraySorter — arraySortOneColumnRange per chunk (PartitionNullsOnly /
+// PartitionNullLikes + stable_sort finites), then pairwise merge (ChunkedMergeImpl-style merge
+// using full row order; C++ splits null / non-null merge when the type has null-likes).
+//
+// Multi-key, aligned chunks: TableSorter — per-chunk RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter, then merge.
+//
+// Multi-key, single segment: RadixRecordBatchSorter (<= maxRadixSortKeys) or
+// MultipleKeyRecordBatchSorter (> maxRadixSortKeys).
+
+// maxRadixSortKeys matches Arrow C++ kMaxRadixSortKeys (vector_sort.cc): above this, one global
+// multi-key stable sort is used instead of MSD radix.
+const maxRadixSortKeys = 8
+
+// columnComparator is the Go analogue of compute::internal::ColumnComparator (vector_sort_internal.h):
+// per-column row compare + null / null-like metadata for partitioning.
+type columnComparator interface {
+ // compareRowsForKey returns -1 if i before j, +1 if i after j, 0 if tied on this column
+ // (both null, or both non-null and equal), so the caller may advance to the next sort key.
+ compareRowsForKey(i, j uint64, key SortKey) int
+ // isNullAt returns true if the global row index is null.
+ isNullAt(global uint64) bool
+ // hasNullLikeValues returns true if the column has null-like values.
+ hasNullLikeValues() bool
+ // isNullLikeAt returns true if the global row index is a null-like value.
+ isNullLikeAt(global uint64) bool
+ // columnHasValidityNulls mirrors Array::null_count() != 0; when false, C++ skips PartitionNullsOnly.
+ columnHasValidityNulls() bool
+}
+
+// multiColumnComparator compares two logical rows (global uint64 indices) lexicographically
+// across every sort key. That matches C++ MultipleKeyComparator::CompareInternal(left, right, 0)
+// (vector_sort_internal.h), but it is not a port of the whole MultipleKeyComparator type: C++ keeps
+// ResolvedSortKey per column, uses Location (int64 batch row vs ChunkLocation on tables), builds
+// virtual ColumnComparator instances, and passes start_sort_key_index for radix tails and other
+// partial key ranges — in Go those suffix compares are makeTailComparator(comparators, keys, from).
+type multiColumnComparator struct {
+ columns []columnComparator
+ keys []SortKey
+}
+
+// compare is a three-way ordering for stable sort / merge: negative if idxA before idxB, etc.
+func (m *multiColumnComparator) compare(idxA, idxB uint64) int {
+ for i, key := range m.keys {
+ if cmpVal := m.columns[i].compareRowsForKey(idxA, idxB, key); cmpVal != 0 {
+ return cmpVal
+ }
+ }
+ return 0
+}
+
+func extensionStorageFixedSizeBinaryChunks(chunks []arrow.Array) ([]arrow.Array, error) {
+ out := make([]arrow.Array, len(chunks))
+ for i, ch := range chunks {
+ ext, ok := ch.(array.ExtensionArray)
+ if !ok {
+ return nil, fmt.Errorf("%w: extension column must implement array.ExtensionArray", arrow.ErrInvalid)
+ }
+ st := ext.Storage()
+ if st.DataType().ID() != arrow.FIXED_SIZE_BINARY {
+ return nil, fmt.Errorf("%w: sorting extension columns is only supported when storage is fixed_size_binary (got %s)",
+ arrow.ErrNotImplemented, st.DataType())
+ }
+ out[i] = st
+ }
+ return out, nil
+}
+
+func newFixedSizeBinaryComparator(chunks []arrow.Array, numRows int, vn bool) (columnComparator, error) {
+ f0, ok := chunks[0].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ w := f0.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ for i := 1; i < len(chunks); i++ {
+ fi, ok := chunks[i].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ wi := fi.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ if wi != w {
+ return nil, fmt.Errorf("%w: fixed_size_binary chunks must have the same byte width (%d vs %d)",
+ arrow.ErrInvalid, w, wi)
+ }
+ }
+ return newPhysicalSortFixedSizeBinaryColumn(chunks, numRows, vn), nil
+}
+
+// createChunkedComparator builds a column comparator for these chunks (one Arrow type for all chunks).
+func createChunkedComparator(chunks []arrow.Array, numRows int) (columnComparator, error) {
+ if len(chunks) == 0 {
+ return nil, fmt.Errorf("%w: cannot create comparator for empty chunk list", arrow.ErrInvalid)
+ }
+ if totalChunkRows(chunks) != numRows {
+ return nil, fmt.Errorf("%w: chunk row count does not match column length", arrow.ErrInvalid)
+ }
+
+ validityNulls := chunksHaveNulls(chunks)
+ typeID := chunks[0].DataType().ID()
+ switch typeID {
+ case arrow.INT8:
+ return newPhysicalSortInt8Column(chunks, numRows, validityNulls), nil
+ case arrow.INT16:
+ return newPhysicalSortInt16Column(chunks, numRows, validityNulls), nil
+ case arrow.INT32:
+ return newPhysicalSortInt32Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE32:
+ return newPhysicalSortDate32Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME32:
+ return newPhysicalSortTime32Column(chunks, numRows, validityNulls), nil
+ case arrow.INT64:
+ return newPhysicalSortInt64Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE64:
+ return newPhysicalSortDate64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME64:
+ return newPhysicalSortTime64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIMESTAMP:
+ return newPhysicalSortTimestampColumn(chunks, numRows, validityNulls), nil
+ case arrow.DURATION:
+ return newPhysicalSortDurationColumn(chunks, numRows, validityNulls), nil
+ case arrow.UINT8:
+ return newPhysicalSortUint8Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT16:
+ return newPhysicalSortUint16Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT32:
+ return newPhysicalSortUint32Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT64:
+ return newPhysicalSortUint64Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT16:
+ return newPhysicalSortFloat16Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT32:
+ return newPhysicalSortFloat32Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT64:
+ return newPhysicalSortFloat64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL32:
+ return newPhysicalSortDecimal32Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL64:
+ return newPhysicalSortDecimal64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL128:
+ return newPhysicalSortDecimal128Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL256:
+ return newPhysicalSortDecimal256Column(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTHS:
+ return newPhysicalSortMonthIntervalColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_DAY_TIME:
+ return newPhysicalSortDayTimeColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTH_DAY_NANO:
+ return newPhysicalSortMonthDayNanoColumn(chunks, numRows, validityNulls), nil
+ case arrow.BOOL:
+ return newPhysicalSortBoolColumn(chunks, numRows, validityNulls), nil
+ case arrow.STRING:
+ return newPhysicalSortStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_STRING:
+ return newPhysicalSortLargeStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.BINARY:
+ return newPhysicalSortBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_BINARY:
+ return newPhysicalSortLargeBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.FIXED_SIZE_BINARY:
+ return newFixedSizeBinaryComparator(chunks, numRows, validityNulls)
+ case arrow.EXTENSION:
+ storageChunks, err := extensionStorageFixedSizeBinaryChunks(chunks)
+ if err != nil {
+ return nil, err
+ }
+ return newFixedSizeBinaryComparator(storageChunks, numRows, validityNulls)
+ default:
+ return nil, fmt.Errorf("%w: sorting not supported for type %s", arrow.ErrNotImplemented, typeID)
+ }
+}
+
+// chunkIndexSpan represents a contiguous range of indices in the global order.
+type chunkIndexSpan struct {
+ lo, hi int
+}
+
+// mergeAdjacentStable merges sorted adjacent ranges [a0,a1) and [b0,b1) (a1 == b0) into indices[lo:hi]
+// using a strict weak order: i is ordered before j iff less(i,j). Tie-breaking prefers the left range
+// (stable merge, same as C++ std::merge with !comp(right,left)).
+func mergeAdjacentStable(indices, tmp []uint64, a0, a1, b0, b1 int, less func(a, b uint64) bool) {
+ i, j, k := a0, b0, a0
+ for i < a1 && j < b1 {
+ if !less(indices[j], indices[i]) {
+ tmp[k] = indices[i]
+ i++
+ } else {
+ tmp[k] = indices[j]
+ j++
+ }
+ k++
+ }
+ for i < a1 {
+ tmp[k] = indices[i]
+ k++
+ i++
+ }
+ for j < b1 {
+ tmp[k] = indices[j]
+ k++
+ j++
+ }
+ copy(indices[a0:b1], tmp[a0:b1])
+}
+
+// pairwiseMergeSortedSpans merges already-sorted adjacent index spans (chunk batch rows in global
+// order), matching Arrow C++ ChunkedMergeImpl / TableSorter batch merge (vector_sort.cc).
+// spanScratch must have capacity >= len(spans); it ping-pongs with spans' backing during merging.
+func pairwiseMergeSortedSpans(indices, tmp []uint64, spans []chunkIndexSpan, less func(a, b uint64) bool, spanScratch []chunkIndexSpan) {
+ if len(spans) <= 1 {
+ return
+ }
+ if cap(spanScratch) < len(spans) {
+ panic("kernels: spanScratch cap < len(spans)")
+ }
+ cur := spans
+ other := spanScratch[:0]
+ for len(cur) > 1 {
+ other = other[:0]
+ for i := 0; i < len(cur); i += 2 {
+ if i+1 < len(cur) {
+ s0, s1 := cur[i], cur[i+1]
+ mergeAdjacentStable(indices, tmp, s0.lo, s0.hi, s1.lo, s1.hi, less)
+ other = append(other, chunkIndexSpan{s0.lo, s1.hi})
+ } else {
+ other = append(other, cur[i])
+ }
+ }
+ cur, other = other, cur
+ }
+}
+
+// alignedChunkBoundaries reports cumulative row offsets for chunk boundaries when every sort column
+// has the same chunk count and matching chunk lengths (typical for Arrow tables).
+func alignedChunkBoundaries(columns []*arrow.Chunked) ([]int, bool) {
+ if len(columns) == 0 {
+ return nil, false
+ }
+ ch0 := columns[0].Chunks()
+ n := len(ch0)
+ if n == 0 {
+ return nil, false
+ }
+ offs := make([]int, n+1)
+ for i := 0; i < n; i++ {
+ L := ch0[i].Len()
+ for j := 1; j < len(columns); j++ {
+ cj := columns[j].Chunks()
+ if len(cj) != n || cj[i].Len() != L {
+ return nil, false
+ }
+ }
+ offs[i+1] = offs[i] + L
+ }
+ if offs[n] != columns[0].Len() {
+ return nil, false
+ }
+ return offs, true
+}
+
+// sortIndicesSingleColumnChunked implements Arrow C++ ChunkedArraySorter for one logical column:
+// per-chunk array sort (partition + sort finites), then pairwise merge (ChunkedMergeImpl).
+func sortIndicesSingleColumnChunked(indices []uint64, chunks []arrow.Array, comp columnComparator, key SortKey, tmp []uint64, spanScratch []chunkIndexSpan) {
+ lo := 0
+ for _, ch := range chunks {
+ hi := lo + ch.Len()
+ arraySortOneColumnRange(indices, tmp, comp, key, lo, hi)
+ lo = hi
+ }
+
+ nChunks := len(chunks)
+ if nChunks <= 1 {
+ return
+ }
+
+ less := func(a, b uint64) bool { return comp.compareRowsForKey(a, b, key) < 0 }
+
+ spans := make([]chunkIndexSpan, nChunks)
+ lo = 0
+ for i, ch := range chunks {
+ hi := lo + ch.Len()
+ spans[i] = chunkIndexSpan{lo, hi}
+ lo = hi
+ }
+ pairwiseMergeSortedSpans(indices, tmp, spans, less, spanScratch)
+}
+
+// sortIndicesMultiColumnAlignedChunks sorts each aligned chunk (C++ RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter), then merges like Arrow C++ TableSorter.
+func sortIndicesMultiColumnAlignedChunks(indices []uint64, offs []int, comparators []columnComparator, keys []SortKey, multiComp *multiColumnComparator, tmp []uint64, spanScratch []chunkIndexSpan) {
+ nChunks := len(offs) - 1
+ useRadix := len(keys) <= maxRadixSortKeys
+ for c := 0; c < nChunks; c++ {
+ lo, hi := offs[c], offs[c+1]
+ if useRadix {
+ radixRecordBatchSortRange(indices, tmp, comparators, keys, 0, lo, hi)
+ } else {
+ multipleKeyRecordBatchSortRange(indices, tmp, comparators, keys, lo, hi, makeTailComparator(comparators, keys, 1))
+ }
+ }
+ if nChunks <= 1 {
+ return
+ }
+ less := func(a, b uint64) bool { return multiComp.compare(a, b) < 0 }
+ spans := make([]chunkIndexSpan, nChunks)
+ for c := 0; c < nChunks; c++ {
+ spans[c] = chunkIndexSpan{offs[c], offs[c+1]}
+ }
+ pairwiseMergeSortedSpans(indices, tmp, spans, less, spanScratch)
+}
+
+// SortIndices returns a stable permutation of 0..n-1 that would lexicographically sort the given
+// columns. Each *arrow.Chunked is used via its .Chunks() only—no concatenate. columns[i] pairs with
+// keys[i] for order and null placement on that column.
+func SortIndices(ctx *exec.KernelCtx, columns []*arrow.Chunked, keys []SortKey) (*exec.ExecResult, error) {
+ if len(columns) == 0 || len(keys) == 0 {
+ return nil, fmt.Errorf("%w: must have at least one column and one sort key", arrow.ErrInvalid)
+ }
+
+ if len(columns) != len(keys) {
+ return nil, fmt.Errorf("%w: number of columns (%d) must match number of sort keys (%d)",
+ arrow.ErrInvalid, len(columns), len(keys))
+ }
+
+ length := int64(columns[0].Len())
+ for _, col := range columns {
+ if int64(col.Len()) != length {
+ return nil, fmt.Errorf("%w: all columns must have the same length", arrow.ErrInvalid)
+ }
+ }
+
+ comparators := make([]columnComparator, len(columns))
+ nRows := int(length)
+ for i, col := range columns {
+ comp, err := createChunkedComparator(col.Chunks(), nRows)
+ if err != nil {
+ return nil, err
+ }
+ comparators[i] = comp
+ }
+
+ multiComp := &multiColumnComparator{
+ columns: comparators,
+ keys: keys,
+ }
+
+ out := &exec.ExecResult{}
+ out.Len = length
+ out.Type = arrow.PrimitiveTypes.Uint64
+ out.Nulls = 0
+
+ buf := ctx.Allocate(int(length) * arrow.Uint64SizeBytes)
+ indices := arrow.Uint64Traits.CastFromBytes(buf.Buf())[:length]
Review Comment:
use `arrow.GetData[uint64](buf.Buf())[:length]` now instead.
##########
arrow/compute/internal/kernels/vector_sort.go:
##########
@@ -0,0 +1,476 @@
+// 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.
+
+//go:build go1.18
+
+package kernels
+
+import (
+ "fmt"
+ "slices"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/compute/exec"
+)
+
+// SortOrder specifies the sort order for sorting operations.
+type SortOrder int8
+
+const (
+ Ascending SortOrder = iota
+ Descending
+)
+
+// NullPlacement specifies where null values should be placed in the sort order.
+type NullPlacement int8
+
+const (
+ NullsAtEnd NullPlacement = iota
+ NullsAtStart
+)
+
+// SortOptions defines options for the sort_indices function.
+type SortOptions struct {
+ Order SortOrder `compute:"order"`
+ NullPlacement NullPlacement `compute:"null_placement"`
+}
+
+func (SortOptions) TypeName() string { return "SortOptions" }
+
+type SortState = SortOptions
+
+// SortKey defines a column to sort by with its ordering and null placement options.
+type SortKey struct {
+ ColumnIndex int
+ Order SortOrder
+ NullPlacement NullPlacement
+}
+
+// Chunk-aware sort_indices: logical row IDs 0..n-1, no chunk concatenation. Structure follows
+// Apache Arrow C++ vector_sort.cc / vector_sort_internal.h (see vector_sort_internal.go).
+//
+// Per-column data uses a dense logicalRowMap for O(1) chunk resolution under random compares.
+// Each sortable physical type has a dedicated comparator struct in vector_sort_physical.go (C++
+// ConcreteColumnComparator<T> shape): full monomorphization for the hot compare path; no
+// value-level compare func pointer.
+// compareRowsForKey implements the same ordering as C++ (null placement, NaN, Order).
+//
+// Single key: ChunkedArraySorter — arraySortOneColumnRange per chunk (PartitionNullsOnly /
+// PartitionNullLikes + stable_sort finites), then pairwise merge (ChunkedMergeImpl-style merge
+// using full row order; C++ splits null / non-null merge when the type has null-likes).
+//
+// Multi-key, aligned chunks: TableSorter — per-chunk RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter, then merge.
+//
+// Multi-key, single segment: RadixRecordBatchSorter (<= maxRadixSortKeys) or
+// MultipleKeyRecordBatchSorter (> maxRadixSortKeys).
+
+// maxRadixSortKeys matches Arrow C++ kMaxRadixSortKeys (vector_sort.cc): above this, one global
+// multi-key stable sort is used instead of MSD radix.
+const maxRadixSortKeys = 8
+
+// columnComparator is the Go analogue of compute::internal::ColumnComparator (vector_sort_internal.h):
+// per-column row compare + null / null-like metadata for partitioning.
+type columnComparator interface {
+ // compareRowsForKey returns -1 if i before j, +1 if i after j, 0 if tied on this column
+ // (both null, or both non-null and equal), so the caller may advance to the next sort key.
+ compareRowsForKey(i, j uint64, key SortKey) int
+ // isNullAt returns true if the global row index is null.
+ isNullAt(global uint64) bool
+ // hasNullLikeValues returns true if the column has null-like values.
+ hasNullLikeValues() bool
+ // isNullLikeAt returns true if the global row index is a null-like value.
+ isNullLikeAt(global uint64) bool
+ // columnHasValidityNulls mirrors Array::null_count() != 0; when false, C++ skips PartitionNullsOnly.
+ columnHasValidityNulls() bool
+}
+
+// multiColumnComparator compares two logical rows (global uint64 indices) lexicographically
+// across every sort key. That matches C++ MultipleKeyComparator::CompareInternal(left, right, 0)
+// (vector_sort_internal.h), but it is not a port of the whole MultipleKeyComparator type: C++ keeps
+// ResolvedSortKey per column, uses Location (int64 batch row vs ChunkLocation on tables), builds
+// virtual ColumnComparator instances, and passes start_sort_key_index for radix tails and other
+// partial key ranges — in Go those suffix compares are makeTailComparator(comparators, keys, from).
+type multiColumnComparator struct {
+ columns []columnComparator
+ keys []SortKey
+}
+
+// compare is a three-way ordering for stable sort / merge: negative if idxA before idxB, etc.
+func (m *multiColumnComparator) compare(idxA, idxB uint64) int {
+ for i, key := range m.keys {
+ if cmpVal := m.columns[i].compareRowsForKey(idxA, idxB, key); cmpVal != 0 {
+ return cmpVal
+ }
+ }
+ return 0
+}
+
+func extensionStorageFixedSizeBinaryChunks(chunks []arrow.Array) ([]arrow.Array, error) {
+ out := make([]arrow.Array, len(chunks))
+ for i, ch := range chunks {
+ ext, ok := ch.(array.ExtensionArray)
+ if !ok {
+ return nil, fmt.Errorf("%w: extension column must implement array.ExtensionArray", arrow.ErrInvalid)
+ }
+ st := ext.Storage()
+ if st.DataType().ID() != arrow.FIXED_SIZE_BINARY {
+ return nil, fmt.Errorf("%w: sorting extension columns is only supported when storage is fixed_size_binary (got %s)",
+ arrow.ErrNotImplemented, st.DataType())
+ }
+ out[i] = st
+ }
+ return out, nil
+}
+
+func newFixedSizeBinaryComparator(chunks []arrow.Array, numRows int, vn bool) (columnComparator, error) {
+ f0, ok := chunks[0].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ w := f0.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ for i := 1; i < len(chunks); i++ {
+ fi, ok := chunks[i].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ wi := fi.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ if wi != w {
+ return nil, fmt.Errorf("%w: fixed_size_binary chunks must have the same byte width (%d vs %d)",
+ arrow.ErrInvalid, w, wi)
+ }
+ }
+ return newPhysicalSortFixedSizeBinaryColumn(chunks, numRows, vn), nil
+}
+
+// createChunkedComparator builds a column comparator for these chunks (one Arrow type for all chunks).
+func createChunkedComparator(chunks []arrow.Array, numRows int) (columnComparator, error) {
+ if len(chunks) == 0 {
+ return nil, fmt.Errorf("%w: cannot create comparator for empty chunk list", arrow.ErrInvalid)
+ }
+ if totalChunkRows(chunks) != numRows {
+ return nil, fmt.Errorf("%w: chunk row count does not match column length", arrow.ErrInvalid)
+ }
+
+ validityNulls := chunksHaveNulls(chunks)
+ typeID := chunks[0].DataType().ID()
+ switch typeID {
+ case arrow.INT8:
+ return newPhysicalSortInt8Column(chunks, numRows, validityNulls), nil
+ case arrow.INT16:
+ return newPhysicalSortInt16Column(chunks, numRows, validityNulls), nil
+ case arrow.INT32:
+ return newPhysicalSortInt32Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE32:
+ return newPhysicalSortDate32Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME32:
+ return newPhysicalSortTime32Column(chunks, numRows, validityNulls), nil
+ case arrow.INT64:
+ return newPhysicalSortInt64Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE64:
+ return newPhysicalSortDate64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME64:
+ return newPhysicalSortTime64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIMESTAMP:
+ return newPhysicalSortTimestampColumn(chunks, numRows, validityNulls), nil
+ case arrow.DURATION:
+ return newPhysicalSortDurationColumn(chunks, numRows, validityNulls), nil
+ case arrow.UINT8:
+ return newPhysicalSortUint8Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT16:
+ return newPhysicalSortUint16Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT32:
+ return newPhysicalSortUint32Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT64:
+ return newPhysicalSortUint64Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT16:
+ return newPhysicalSortFloat16Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT32:
+ return newPhysicalSortFloat32Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT64:
+ return newPhysicalSortFloat64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL32:
+ return newPhysicalSortDecimal32Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL64:
+ return newPhysicalSortDecimal64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL128:
+ return newPhysicalSortDecimal128Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL256:
+ return newPhysicalSortDecimal256Column(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTHS:
+ return newPhysicalSortMonthIntervalColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_DAY_TIME:
+ return newPhysicalSortDayTimeColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTH_DAY_NANO:
+ return newPhysicalSortMonthDayNanoColumn(chunks, numRows, validityNulls), nil
+ case arrow.BOOL:
+ return newPhysicalSortBoolColumn(chunks, numRows, validityNulls), nil
+ case arrow.STRING:
+ return newPhysicalSortStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_STRING:
+ return newPhysicalSortLargeStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.BINARY:
+ return newPhysicalSortBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_BINARY:
+ return newPhysicalSortLargeBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.FIXED_SIZE_BINARY:
+ return newFixedSizeBinaryComparator(chunks, numRows, validityNulls)
+ case arrow.EXTENSION:
+ storageChunks, err := extensionStorageFixedSizeBinaryChunks(chunks)
+ if err != nil {
+ return nil, err
+ }
+ return newFixedSizeBinaryComparator(storageChunks, numRows, validityNulls)
+ default:
+ return nil, fmt.Errorf("%w: sorting not supported for type %s", arrow.ErrNotImplemented, typeID)
+ }
+}
+
+// chunkIndexSpan represents a contiguous range of indices in the global order.
+type chunkIndexSpan struct {
+ lo, hi int
+}
+
+// mergeAdjacentStable merges sorted adjacent ranges [a0,a1) and [b0,b1) (a1 == b0) into indices[lo:hi]
+// using a strict weak order: i is ordered before j iff less(i,j). Tie-breaking prefers the left range
+// (stable merge, same as C++ std::merge with !comp(right,left)).
+func mergeAdjacentStable(indices, tmp []uint64, a0, a1, b0, b1 int, less func(a, b uint64) bool) {
+ i, j, k := a0, b0, a0
+ for i < a1 && j < b1 {
+ if !less(indices[j], indices[i]) {
+ tmp[k] = indices[i]
+ i++
+ } else {
+ tmp[k] = indices[j]
+ j++
+ }
+ k++
+ }
+ for i < a1 {
+ tmp[k] = indices[i]
+ k++
+ i++
+ }
+ for j < b1 {
+ tmp[k] = indices[j]
+ k++
+ j++
+ }
+ copy(indices[a0:b1], tmp[a0:b1])
+}
+
+// pairwiseMergeSortedSpans merges already-sorted adjacent index spans (chunk batch rows in global
+// order), matching Arrow C++ ChunkedMergeImpl / TableSorter batch merge (vector_sort.cc).
+// spanScratch must have capacity >= len(spans); it ping-pongs with spans' backing during merging.
+func pairwiseMergeSortedSpans(indices, tmp []uint64, spans []chunkIndexSpan, less func(a, b uint64) bool, spanScratch []chunkIndexSpan) {
+ if len(spans) <= 1 {
+ return
+ }
+ if cap(spanScratch) < len(spans) {
+ panic("kernels: spanScratch cap < len(spans)")
+ }
+ cur := spans
+ other := spanScratch[:0]
+ for len(cur) > 1 {
+ other = other[:0]
+ for i := 0; i < len(cur); i += 2 {
+ if i+1 < len(cur) {
+ s0, s1 := cur[i], cur[i+1]
+ mergeAdjacentStable(indices, tmp, s0.lo, s0.hi, s1.lo, s1.hi, less)
+ other = append(other, chunkIndexSpan{s0.lo, s1.hi})
+ } else {
+ other = append(other, cur[i])
+ }
+ }
+ cur, other = other, cur
+ }
+}
+
+// alignedChunkBoundaries reports cumulative row offsets for chunk boundaries when every sort column
+// has the same chunk count and matching chunk lengths (typical for Arrow tables).
+func alignedChunkBoundaries(columns []*arrow.Chunked) ([]int, bool) {
+ if len(columns) == 0 {
+ return nil, false
+ }
+ ch0 := columns[0].Chunks()
+ n := len(ch0)
+ if n == 0 {
+ return nil, false
+ }
+ offs := make([]int, n+1)
+ for i := 0; i < n; i++ {
Review Comment:
```suggestion
for i := range n {
```
##########
arrow/compute/internal/kernels/vector_sort.go:
##########
@@ -0,0 +1,476 @@
+// 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.
+
+//go:build go1.18
+
+package kernels
+
+import (
+ "fmt"
+ "slices"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/compute/exec"
+)
+
+// SortOrder specifies the sort order for sorting operations.
+type SortOrder int8
+
+const (
+ Ascending SortOrder = iota
+ Descending
+)
+
+// NullPlacement specifies where null values should be placed in the sort order.
+type NullPlacement int8
+
+const (
+ NullsAtEnd NullPlacement = iota
+ NullsAtStart
+)
+
+// SortOptions defines options for the sort_indices function.
+type SortOptions struct {
+ Order SortOrder `compute:"order"`
+ NullPlacement NullPlacement `compute:"null_placement"`
+}
+
+func (SortOptions) TypeName() string { return "SortOptions" }
+
+type SortState = SortOptions
+
+// SortKey defines a column to sort by with its ordering and null placement options.
+type SortKey struct {
+ ColumnIndex int
+ Order SortOrder
+ NullPlacement NullPlacement
+}
+
+// Chunk-aware sort_indices: logical row IDs 0..n-1, no chunk concatenation. Structure follows
+// Apache Arrow C++ vector_sort.cc / vector_sort_internal.h (see vector_sort_internal.go).
+//
+// Per-column data uses a dense logicalRowMap for O(1) chunk resolution under random compares.
+// Each sortable physical type has a dedicated comparator struct in vector_sort_physical.go (C++
+// ConcreteColumnComparator<T> shape): full monomorphization for the hot compare path; no
+// value-level compare func pointer.
+// compareRowsForKey implements the same ordering as C++ (null placement, NaN, Order).
+//
+// Single key: ChunkedArraySorter — arraySortOneColumnRange per chunk (PartitionNullsOnly /
+// PartitionNullLikes + stable_sort finites), then pairwise merge (ChunkedMergeImpl-style merge
+// using full row order; C++ splits null / non-null merge when the type has null-likes).
+//
+// Multi-key, aligned chunks: TableSorter — per-chunk RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter, then merge.
+//
+// Multi-key, single segment: RadixRecordBatchSorter (<= maxRadixSortKeys) or
+// MultipleKeyRecordBatchSorter (> maxRadixSortKeys).
+
+// maxRadixSortKeys matches Arrow C++ kMaxRadixSortKeys (vector_sort.cc): above this, one global
+// multi-key stable sort is used instead of MSD radix.
+const maxRadixSortKeys = 8
+
+// columnComparator is the Go analogue of compute::internal::ColumnComparator (vector_sort_internal.h):
+// per-column row compare + null / null-like metadata for partitioning.
+type columnComparator interface {
+ // compareRowsForKey returns -1 if i before j, +1 if i after j, 0 if tied on this column
+ // (both null, or both non-null and equal), so the caller may advance to the next sort key.
+ compareRowsForKey(i, j uint64, key SortKey) int
+ // isNullAt returns true if the global row index is null.
+ isNullAt(global uint64) bool
+ // hasNullLikeValues returns true if the column has null-like values.
+ hasNullLikeValues() bool
+ // isNullLikeAt returns true if the global row index is a null-like value.
+ isNullLikeAt(global uint64) bool
+ // columnHasValidityNulls mirrors Array::null_count() != 0; when false, C++ skips PartitionNullsOnly.
+ columnHasValidityNulls() bool
+}
+
+// multiColumnComparator compares two logical rows (global uint64 indices) lexicographically
+// across every sort key. That matches C++ MultipleKeyComparator::CompareInternal(left, right, 0)
+// (vector_sort_internal.h), but it is not a port of the whole MultipleKeyComparator type: C++ keeps
+// ResolvedSortKey per column, uses Location (int64 batch row vs ChunkLocation on tables), builds
+// virtual ColumnComparator instances, and passes start_sort_key_index for radix tails and other
+// partial key ranges — in Go those suffix compares are makeTailComparator(comparators, keys, from).
+type multiColumnComparator struct {
+ columns []columnComparator
+ keys []SortKey
+}
+
+// compare is a three-way ordering for stable sort / merge: negative if idxA before idxB, etc.
+func (m *multiColumnComparator) compare(idxA, idxB uint64) int {
+ for i, key := range m.keys {
+ if cmpVal := m.columns[i].compareRowsForKey(idxA, idxB, key); cmpVal != 0 {
+ return cmpVal
+ }
+ }
+ return 0
+}
+
+func extensionStorageFixedSizeBinaryChunks(chunks []arrow.Array) ([]arrow.Array, error) {
+ out := make([]arrow.Array, len(chunks))
+ for i, ch := range chunks {
+ ext, ok := ch.(array.ExtensionArray)
+ if !ok {
+ return nil, fmt.Errorf("%w: extension column must implement array.ExtensionArray", arrow.ErrInvalid)
+ }
+ st := ext.Storage()
+ if st.DataType().ID() != arrow.FIXED_SIZE_BINARY {
+ return nil, fmt.Errorf("%w: sorting extension columns is only supported when storage is fixed_size_binary (got %s)",
+ arrow.ErrNotImplemented, st.DataType())
+ }
+ out[i] = st
+ }
+ return out, nil
+}
+
+func newFixedSizeBinaryComparator(chunks []arrow.Array, numRows int, vn bool) (columnComparator, error) {
+ f0, ok := chunks[0].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ w := f0.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ for i := 1; i < len(chunks); i++ {
+ fi, ok := chunks[i].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ wi := fi.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ if wi != w {
+ return nil, fmt.Errorf("%w: fixed_size_binary chunks must have the same byte width (%d vs %d)",
+ arrow.ErrInvalid, w, wi)
+ }
+ }
+ return newPhysicalSortFixedSizeBinaryColumn(chunks, numRows, vn), nil
+}
+
+// createChunkedComparator builds a column comparator for these chunks (one Arrow type for all chunks).
+func createChunkedComparator(chunks []arrow.Array, numRows int) (columnComparator, error) {
+ if len(chunks) == 0 {
+ return nil, fmt.Errorf("%w: cannot create comparator for empty chunk list", arrow.ErrInvalid)
+ }
+ if totalChunkRows(chunks) != numRows {
+ return nil, fmt.Errorf("%w: chunk row count does not match column length", arrow.ErrInvalid)
+ }
+
+ validityNulls := chunksHaveNulls(chunks)
+ typeID := chunks[0].DataType().ID()
+ switch typeID {
+ case arrow.INT8:
+ return newPhysicalSortInt8Column(chunks, numRows, validityNulls), nil
+ case arrow.INT16:
+ return newPhysicalSortInt16Column(chunks, numRows, validityNulls), nil
+ case arrow.INT32:
+ return newPhysicalSortInt32Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE32:
+ return newPhysicalSortDate32Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME32:
+ return newPhysicalSortTime32Column(chunks, numRows, validityNulls), nil
+ case arrow.INT64:
+ return newPhysicalSortInt64Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE64:
+ return newPhysicalSortDate64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME64:
+ return newPhysicalSortTime64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIMESTAMP:
+ return newPhysicalSortTimestampColumn(chunks, numRows, validityNulls), nil
+ case arrow.DURATION:
+ return newPhysicalSortDurationColumn(chunks, numRows, validityNulls), nil
+ case arrow.UINT8:
+ return newPhysicalSortUint8Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT16:
+ return newPhysicalSortUint16Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT32:
+ return newPhysicalSortUint32Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT64:
+ return newPhysicalSortUint64Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT16:
+ return newPhysicalSortFloat16Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT32:
+ return newPhysicalSortFloat32Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT64:
+ return newPhysicalSortFloat64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL32:
+ return newPhysicalSortDecimal32Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL64:
+ return newPhysicalSortDecimal64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL128:
+ return newPhysicalSortDecimal128Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL256:
+ return newPhysicalSortDecimal256Column(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTHS:
+ return newPhysicalSortMonthIntervalColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_DAY_TIME:
+ return newPhysicalSortDayTimeColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTH_DAY_NANO:
+ return newPhysicalSortMonthDayNanoColumn(chunks, numRows, validityNulls), nil
+ case arrow.BOOL:
+ return newPhysicalSortBoolColumn(chunks, numRows, validityNulls), nil
+ case arrow.STRING:
+ return newPhysicalSortStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_STRING:
+ return newPhysicalSortLargeStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.BINARY:
+ return newPhysicalSortBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_BINARY:
+ return newPhysicalSortLargeBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.FIXED_SIZE_BINARY:
+ return newFixedSizeBinaryComparator(chunks, numRows, validityNulls)
+ case arrow.EXTENSION:
+ storageChunks, err := extensionStorageFixedSizeBinaryChunks(chunks)
+ if err != nil {
+ return nil, err
+ }
+ return newFixedSizeBinaryComparator(storageChunks, numRows, validityNulls)
+ default:
+ return nil, fmt.Errorf("%w: sorting not supported for type %s", arrow.ErrNotImplemented, typeID)
+ }
+}
+
+// chunkIndexSpan represents a contiguous range of indices in the global order.
+type chunkIndexSpan struct {
+ lo, hi int
+}
+
+// mergeAdjacentStable merges sorted adjacent ranges [a0,a1) and [b0,b1) (a1 == b0) into indices[lo:hi]
+// using a strict weak order: i is ordered before j iff less(i,j). Tie-breaking prefers the left range
+// (stable merge, same as C++ std::merge with !comp(right,left)).
+func mergeAdjacentStable(indices, tmp []uint64, a0, a1, b0, b1 int, less func(a, b uint64) bool) {
+ i, j, k := a0, b0, a0
+ for i < a1 && j < b1 {
+ if !less(indices[j], indices[i]) {
+ tmp[k] = indices[i]
+ i++
+ } else {
+ tmp[k] = indices[j]
+ j++
+ }
+ k++
+ }
+ for i < a1 {
+ tmp[k] = indices[i]
+ k++
+ i++
+ }
+ for j < b1 {
+ tmp[k] = indices[j]
+ k++
+ j++
+ }
+ copy(indices[a0:b1], tmp[a0:b1])
+}
+
+// pairwiseMergeSortedSpans merges already-sorted adjacent index spans (chunk batch rows in global
+// order), matching Arrow C++ ChunkedMergeImpl / TableSorter batch merge (vector_sort.cc).
+// spanScratch must have capacity >= len(spans); it ping-pongs with spans' backing during merging.
+func pairwiseMergeSortedSpans(indices, tmp []uint64, spans []chunkIndexSpan, less func(a, b uint64) bool, spanScratch []chunkIndexSpan) {
+ if len(spans) <= 1 {
+ return
+ }
+ if cap(spanScratch) < len(spans) {
+ panic("kernels: spanScratch cap < len(spans)")
+ }
+ cur := spans
+ other := spanScratch[:0]
+ for len(cur) > 1 {
+ other = other[:0]
+ for i := 0; i < len(cur); i += 2 {
+ if i+1 < len(cur) {
+ s0, s1 := cur[i], cur[i+1]
+ mergeAdjacentStable(indices, tmp, s0.lo, s0.hi, s1.lo, s1.hi, less)
+ other = append(other, chunkIndexSpan{s0.lo, s1.hi})
+ } else {
+ other = append(other, cur[i])
+ }
+ }
+ cur, other = other, cur
+ }
+}
+
+// alignedChunkBoundaries reports cumulative row offsets for chunk boundaries when every sort column
+// has the same chunk count and matching chunk lengths (typical for Arrow tables).
+func alignedChunkBoundaries(columns []*arrow.Chunked) ([]int, bool) {
+ if len(columns) == 0 {
+ return nil, false
+ }
+ ch0 := columns[0].Chunks()
+ n := len(ch0)
+ if n == 0 {
+ return nil, false
+ }
+ offs := make([]int, n+1)
+ for i := 0; i < n; i++ {
+ L := ch0[i].Len()
+ for j := 1; j < len(columns); j++ {
+ cj := columns[j].Chunks()
Review Comment:
```suggestion
for _, col := range columns[1:] {
cj := col.Chunks()
```
##########
arrow/compute/internal/kernels/vector_sort.go:
##########
@@ -0,0 +1,476 @@
+// 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.
+
+//go:build go1.18
+
+package kernels
+
+import (
+ "fmt"
+ "slices"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/compute/exec"
+)
+
+// SortOrder specifies the sort order for sorting operations.
+type SortOrder int8
+
+const (
+ Ascending SortOrder = iota
+ Descending
+)
+
+// NullPlacement specifies where null values should be placed in the sort order.
+type NullPlacement int8
+
+const (
+ NullsAtEnd NullPlacement = iota
+ NullsAtStart
+)
+
+// SortOptions defines options for the sort_indices function.
+type SortOptions struct {
+ Order SortOrder `compute:"order"`
+ NullPlacement NullPlacement `compute:"null_placement"`
+}
+
+func (SortOptions) TypeName() string { return "SortOptions" }
+
+type SortState = SortOptions
+
+// SortKey defines a column to sort by with its ordering and null placement options.
+type SortKey struct {
+ ColumnIndex int
+ Order SortOrder
+ NullPlacement NullPlacement
+}
+
+// Chunk-aware sort_indices: logical row IDs 0..n-1, no chunk concatenation. Structure follows
+// Apache Arrow C++ vector_sort.cc / vector_sort_internal.h (see vector_sort_internal.go).
+//
+// Per-column data uses a dense logicalRowMap for O(1) chunk resolution under random compares.
+// Each sortable physical type has a dedicated comparator struct in vector_sort_physical.go (C++
+// ConcreteColumnComparator<T> shape): full monomorphization for the hot compare path; no
+// value-level compare func pointer.
+// compareRowsForKey implements the same ordering as C++ (null placement, NaN, Order).
+//
+// Single key: ChunkedArraySorter — arraySortOneColumnRange per chunk (PartitionNullsOnly /
+// PartitionNullLikes + stable_sort finites), then pairwise merge (ChunkedMergeImpl-style merge
+// using full row order; C++ splits null / non-null merge when the type has null-likes).
+//
+// Multi-key, aligned chunks: TableSorter — per-chunk RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter, then merge.
+//
+// Multi-key, single segment: RadixRecordBatchSorter (<= maxRadixSortKeys) or
+// MultipleKeyRecordBatchSorter (> maxRadixSortKeys).
+
+// maxRadixSortKeys matches Arrow C++ kMaxRadixSortKeys (vector_sort.cc): above this, one global
+// multi-key stable sort is used instead of MSD radix.
+const maxRadixSortKeys = 8
+
+// columnComparator is the Go analogue of compute::internal::ColumnComparator (vector_sort_internal.h):
+// per-column row compare + null / null-like metadata for partitioning.
+type columnComparator interface {
+ // compareRowsForKey returns -1 if i before j, +1 if i after j, 0 if tied on this column
+ // (both null, or both non-null and equal), so the caller may advance to the next sort key.
+ compareRowsForKey(i, j uint64, key SortKey) int
+ // isNullAt returns true if the global row index is null.
+ isNullAt(global uint64) bool
+ // hasNullLikeValues returns true if the column has null-like values.
+ hasNullLikeValues() bool
+ // isNullLikeAt returns true if the global row index is a null-like value.
+ isNullLikeAt(global uint64) bool
+ // columnHasValidityNulls mirrors Array::null_count() != 0; when false, C++ skips PartitionNullsOnly.
+ columnHasValidityNulls() bool
+}
+
+// multiColumnComparator compares two logical rows (global uint64 indices) lexicographically
+// across every sort key. That matches C++ MultipleKeyComparator::CompareInternal(left, right, 0)
+// (vector_sort_internal.h), but it is not a port of the whole MultipleKeyComparator type: C++ keeps
+// ResolvedSortKey per column, uses Location (int64 batch row vs ChunkLocation on tables), builds
+// virtual ColumnComparator instances, and passes start_sort_key_index for radix tails and other
+// partial key ranges — in Go those suffix compares are makeTailComparator(comparators, keys, from).
+type multiColumnComparator struct {
+ columns []columnComparator
+ keys []SortKey
+}
+
+// compare is a three-way ordering for stable sort / merge: negative if idxA before idxB, etc.
+func (m *multiColumnComparator) compare(idxA, idxB uint64) int {
+ for i, key := range m.keys {
+ if cmpVal := m.columns[i].compareRowsForKey(idxA, idxB, key); cmpVal != 0 {
+ return cmpVal
+ }
+ }
+ return 0
+}
+
+func extensionStorageFixedSizeBinaryChunks(chunks []arrow.Array) ([]arrow.Array, error) {
+ out := make([]arrow.Array, len(chunks))
+ for i, ch := range chunks {
+ ext, ok := ch.(array.ExtensionArray)
+ if !ok {
+ return nil, fmt.Errorf("%w: extension column must implement array.ExtensionArray", arrow.ErrInvalid)
+ }
+ st := ext.Storage()
+ if st.DataType().ID() != arrow.FIXED_SIZE_BINARY {
+ return nil, fmt.Errorf("%w: sorting extension columns is only supported when storage is fixed_size_binary (got %s)",
+ arrow.ErrNotImplemented, st.DataType())
+ }
+ out[i] = st
+ }
+ return out, nil
+}
+
+func newFixedSizeBinaryComparator(chunks []arrow.Array, numRows int, vn bool) (columnComparator, error) {
+ f0, ok := chunks[0].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ w := f0.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ for i := 1; i < len(chunks); i++ {
+ fi, ok := chunks[i].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ wi := fi.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ if wi != w {
+ return nil, fmt.Errorf("%w: fixed_size_binary chunks must have the same byte width (%d vs %d)",
+ arrow.ErrInvalid, w, wi)
+ }
+ }
+ return newPhysicalSortFixedSizeBinaryColumn(chunks, numRows, vn), nil
+}
+
+// createChunkedComparator builds a column comparator for these chunks (one Arrow type for all chunks).
+func createChunkedComparator(chunks []arrow.Array, numRows int) (columnComparator, error) {
+ if len(chunks) == 0 {
+ return nil, fmt.Errorf("%w: cannot create comparator for empty chunk list", arrow.ErrInvalid)
+ }
+ if totalChunkRows(chunks) != numRows {
+ return nil, fmt.Errorf("%w: chunk row count does not match column length", arrow.ErrInvalid)
+ }
+
+ validityNulls := chunksHaveNulls(chunks)
+ typeID := chunks[0].DataType().ID()
+ switch typeID {
+ case arrow.INT8:
+ return newPhysicalSortInt8Column(chunks, numRows, validityNulls), nil
+ case arrow.INT16:
+ return newPhysicalSortInt16Column(chunks, numRows, validityNulls), nil
+ case arrow.INT32:
+ return newPhysicalSortInt32Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE32:
+ return newPhysicalSortDate32Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME32:
+ return newPhysicalSortTime32Column(chunks, numRows, validityNulls), nil
+ case arrow.INT64:
+ return newPhysicalSortInt64Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE64:
+ return newPhysicalSortDate64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME64:
+ return newPhysicalSortTime64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIMESTAMP:
+ return newPhysicalSortTimestampColumn(chunks, numRows, validityNulls), nil
+ case arrow.DURATION:
+ return newPhysicalSortDurationColumn(chunks, numRows, validityNulls), nil
+ case arrow.UINT8:
+ return newPhysicalSortUint8Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT16:
+ return newPhysicalSortUint16Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT32:
+ return newPhysicalSortUint32Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT64:
+ return newPhysicalSortUint64Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT16:
+ return newPhysicalSortFloat16Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT32:
+ return newPhysicalSortFloat32Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT64:
+ return newPhysicalSortFloat64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL32:
+ return newPhysicalSortDecimal32Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL64:
+ return newPhysicalSortDecimal64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL128:
+ return newPhysicalSortDecimal128Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL256:
+ return newPhysicalSortDecimal256Column(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTHS:
+ return newPhysicalSortMonthIntervalColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_DAY_TIME:
+ return newPhysicalSortDayTimeColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTH_DAY_NANO:
+ return newPhysicalSortMonthDayNanoColumn(chunks, numRows, validityNulls), nil
+ case arrow.BOOL:
+ return newPhysicalSortBoolColumn(chunks, numRows, validityNulls), nil
+ case arrow.STRING:
+ return newPhysicalSortStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_STRING:
+ return newPhysicalSortLargeStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.BINARY:
+ return newPhysicalSortBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_BINARY:
+ return newPhysicalSortLargeBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.FIXED_SIZE_BINARY:
+ return newFixedSizeBinaryComparator(chunks, numRows, validityNulls)
+ case arrow.EXTENSION:
+ storageChunks, err := extensionStorageFixedSizeBinaryChunks(chunks)
+ if err != nil {
+ return nil, err
+ }
+ return newFixedSizeBinaryComparator(storageChunks, numRows, validityNulls)
+ default:
+ return nil, fmt.Errorf("%w: sorting not supported for type %s", arrow.ErrNotImplemented, typeID)
+ }
+}
+
+// chunkIndexSpan represents a contiguous range of indices in the global order.
+type chunkIndexSpan struct {
+ lo, hi int
+}
+
+// mergeAdjacentStable merges sorted adjacent ranges [a0,a1) and [b0,b1) (a1 == b0) into indices[lo:hi]
+// using a strict weak order: i is ordered before j iff less(i,j). Tie-breaking prefers the left range
+// (stable merge, same as C++ std::merge with !comp(right,left)).
+func mergeAdjacentStable(indices, tmp []uint64, a0, a1, b0, b1 int, less func(a, b uint64) bool) {
+ i, j, k := a0, b0, a0
+ for i < a1 && j < b1 {
+ if !less(indices[j], indices[i]) {
+ tmp[k] = indices[i]
+ i++
+ } else {
+ tmp[k] = indices[j]
+ j++
+ }
+ k++
+ }
+ for i < a1 {
+ tmp[k] = indices[i]
+ k++
+ i++
+ }
+ for j < b1 {
+ tmp[k] = indices[j]
+ k++
+ j++
+ }
+ copy(indices[a0:b1], tmp[a0:b1])
+}
+
+// pairwiseMergeSortedSpans merges already-sorted adjacent index spans (chunk batch rows in global
+// order), matching Arrow C++ ChunkedMergeImpl / TableSorter batch merge (vector_sort.cc).
+// spanScratch must have capacity >= len(spans); it ping-pongs with spans' backing during merging.
+func pairwiseMergeSortedSpans(indices, tmp []uint64, spans []chunkIndexSpan, less func(a, b uint64) bool, spanScratch []chunkIndexSpan) {
+ if len(spans) <= 1 {
+ return
+ }
+ if cap(spanScratch) < len(spans) {
+ panic("kernels: spanScratch cap < len(spans)")
+ }
+ cur := spans
+ other := spanScratch[:0]
+ for len(cur) > 1 {
+ other = other[:0]
+ for i := 0; i < len(cur); i += 2 {
+ if i+1 < len(cur) {
+ s0, s1 := cur[i], cur[i+1]
+ mergeAdjacentStable(indices, tmp, s0.lo, s0.hi, s1.lo, s1.hi, less)
+ other = append(other, chunkIndexSpan{s0.lo, s1.hi})
+ } else {
+ other = append(other, cur[i])
+ }
+ }
+ cur, other = other, cur
+ }
+}
+
+// alignedChunkBoundaries reports cumulative row offsets for chunk boundaries when every sort column
+// has the same chunk count and matching chunk lengths (typical for Arrow tables).
+func alignedChunkBoundaries(columns []*arrow.Chunked) ([]int, bool) {
+ if len(columns) == 0 {
+ return nil, false
+ }
+ ch0 := columns[0].Chunks()
+ n := len(ch0)
+ if n == 0 {
+ return nil, false
+ }
+ offs := make([]int, n+1)
+ for i := 0; i < n; i++ {
+ L := ch0[i].Len()
+ for j := 1; j < len(columns); j++ {
+ cj := columns[j].Chunks()
+ if len(cj) != n || cj[i].Len() != L {
+ return nil, false
+ }
+ }
+ offs[i+1] = offs[i] + L
+ }
+ if offs[n] != columns[0].Len() {
+ return nil, false
+ }
+ return offs, true
+}
+
+// sortIndicesSingleColumnChunked implements Arrow C++ ChunkedArraySorter for one logical column:
+// per-chunk array sort (partition + sort finites), then pairwise merge (ChunkedMergeImpl).
+func sortIndicesSingleColumnChunked(indices []uint64, chunks []arrow.Array, comp columnComparator, key SortKey, tmp []uint64, spanScratch []chunkIndexSpan) {
+ lo := 0
+ for _, ch := range chunks {
+ hi := lo + ch.Len()
+ arraySortOneColumnRange(indices, tmp, comp, key, lo, hi)
+ lo = hi
+ }
+
+ nChunks := len(chunks)
+ if nChunks <= 1 {
+ return
+ }
+
+ less := func(a, b uint64) bool { return comp.compareRowsForKey(a, b, key) < 0 }
+
+ spans := make([]chunkIndexSpan, nChunks)
+ lo = 0
+ for i, ch := range chunks {
+ hi := lo + ch.Len()
+ spans[i] = chunkIndexSpan{lo, hi}
+ lo = hi
+ }
+ pairwiseMergeSortedSpans(indices, tmp, spans, less, spanScratch)
+}
+
+// sortIndicesMultiColumnAlignedChunks sorts each aligned chunk (C++ RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter), then merges like Arrow C++ TableSorter.
+func sortIndicesMultiColumnAlignedChunks(indices []uint64, offs []int, comparators []columnComparator, keys []SortKey, multiComp *multiColumnComparator, tmp []uint64, spanScratch []chunkIndexSpan) {
+ nChunks := len(offs) - 1
+ useRadix := len(keys) <= maxRadixSortKeys
+ for c := 0; c < nChunks; c++ {
Review Comment:
```suggestion
for c := range nChunks {
```
##########
arrow/compute/internal/kernels/vector_sort.go:
##########
@@ -0,0 +1,476 @@
+// 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.
+
+//go:build go1.18
+
+package kernels
+
+import (
+ "fmt"
+ "slices"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/compute/exec"
+)
+
+// SortOrder specifies the sort order for sorting operations.
+type SortOrder int8
+
+const (
+ Ascending SortOrder = iota
+ Descending
+)
+
+// NullPlacement specifies where null values should be placed in the sort order.
+type NullPlacement int8
+
+const (
+ NullsAtEnd NullPlacement = iota
+ NullsAtStart
+)
+
+// SortOptions defines options for the sort_indices function.
+type SortOptions struct {
+ Order SortOrder `compute:"order"`
+ NullPlacement NullPlacement `compute:"null_placement"`
+}
+
+func (SortOptions) TypeName() string { return "SortOptions" }
+
+type SortState = SortOptions
+
+// SortKey defines a column to sort by with its ordering and null placement options.
+type SortKey struct {
+ ColumnIndex int
+ Order SortOrder
+ NullPlacement NullPlacement
+}
+
+// Chunk-aware sort_indices: logical row IDs 0..n-1, no chunk concatenation. Structure follows
+// Apache Arrow C++ vector_sort.cc / vector_sort_internal.h (see vector_sort_internal.go).
+//
+// Per-column data uses a dense logicalRowMap for O(1) chunk resolution under random compares.
+// Each sortable physical type has a dedicated comparator struct in vector_sort_physical.go (C++
+// ConcreteColumnComparator<T> shape): full monomorphization for the hot compare path; no
+// value-level compare func pointer.
+// compareRowsForKey implements the same ordering as C++ (null placement, NaN, Order).
+//
+// Single key: ChunkedArraySorter — arraySortOneColumnRange per chunk (PartitionNullsOnly /
+// PartitionNullLikes + stable_sort finites), then pairwise merge (ChunkedMergeImpl-style merge
+// using full row order; C++ splits null / non-null merge when the type has null-likes).
+//
+// Multi-key, aligned chunks: TableSorter — per-chunk RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter, then merge.
+//
+// Multi-key, single segment: RadixRecordBatchSorter (<= maxRadixSortKeys) or
+// MultipleKeyRecordBatchSorter (> maxRadixSortKeys).
+
+// maxRadixSortKeys matches Arrow C++ kMaxRadixSortKeys (vector_sort.cc): above this, one global
+// multi-key stable sort is used instead of MSD radix.
+const maxRadixSortKeys = 8
+
+// columnComparator is the Go analogue of compute::internal::ColumnComparator (vector_sort_internal.h):
+// per-column row compare + null / null-like metadata for partitioning.
+type columnComparator interface {
+ // compareRowsForKey returns -1 if i before j, +1 if i after j, 0 if tied on this column
+ // (both null, or both non-null and equal), so the caller may advance to the next sort key.
+ compareRowsForKey(i, j uint64, key SortKey) int
+ // isNullAt returns true if the global row index is null.
+ isNullAt(global uint64) bool
+ // hasNullLikeValues returns true if the column has null-like values.
+ hasNullLikeValues() bool
+ // isNullLikeAt returns true if the global row index is a null-like value.
+ isNullLikeAt(global uint64) bool
+ // columnHasValidityNulls mirrors Array::null_count() != 0; when false, C++ skips PartitionNullsOnly.
+ columnHasValidityNulls() bool
+}
+
+// multiColumnComparator compares two logical rows (global uint64 indices) lexicographically
+// across every sort key. That matches C++ MultipleKeyComparator::CompareInternal(left, right, 0)
+// (vector_sort_internal.h), but it is not a port of the whole MultipleKeyComparator type: C++ keeps
+// ResolvedSortKey per column, uses Location (int64 batch row vs ChunkLocation on tables), builds
+// virtual ColumnComparator instances, and passes start_sort_key_index for radix tails and other
+// partial key ranges — in Go those suffix compares are makeTailComparator(comparators, keys, from).
+type multiColumnComparator struct {
+ columns []columnComparator
+ keys []SortKey
+}
+
+// compare is a three-way ordering for stable sort / merge: negative if idxA before idxB, etc.
+func (m *multiColumnComparator) compare(idxA, idxB uint64) int {
+ for i, key := range m.keys {
+ if cmpVal := m.columns[i].compareRowsForKey(idxA, idxB, key); cmpVal != 0 {
+ return cmpVal
+ }
+ }
+ return 0
+}
+
+func extensionStorageFixedSizeBinaryChunks(chunks []arrow.Array) ([]arrow.Array, error) {
+ out := make([]arrow.Array, len(chunks))
+ for i, ch := range chunks {
+ ext, ok := ch.(array.ExtensionArray)
+ if !ok {
+ return nil, fmt.Errorf("%w: extension column must implement array.ExtensionArray", arrow.ErrInvalid)
+ }
+ st := ext.Storage()
+ if st.DataType().ID() != arrow.FIXED_SIZE_BINARY {
+ return nil, fmt.Errorf("%w: sorting extension columns is only supported when storage is fixed_size_binary (got %s)",
+ arrow.ErrNotImplemented, st.DataType())
+ }
+ out[i] = st
+ }
+ return out, nil
+}
+
+func newFixedSizeBinaryComparator(chunks []arrow.Array, numRows int, vn bool) (columnComparator, error) {
+ f0, ok := chunks[0].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ w := f0.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ for i := 1; i < len(chunks); i++ {
+ fi, ok := chunks[i].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ wi := fi.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ if wi != w {
+ return nil, fmt.Errorf("%w: fixed_size_binary chunks must have the same byte width (%d vs %d)",
+ arrow.ErrInvalid, w, wi)
+ }
+ }
+ return newPhysicalSortFixedSizeBinaryColumn(chunks, numRows, vn), nil
+}
+
+// createChunkedComparator builds a column comparator for these chunks (one Arrow type for all chunks).
+func createChunkedComparator(chunks []arrow.Array, numRows int) (columnComparator, error) {
+ if len(chunks) == 0 {
+ return nil, fmt.Errorf("%w: cannot create comparator for empty chunk list", arrow.ErrInvalid)
+ }
+ if totalChunkRows(chunks) != numRows {
+ return nil, fmt.Errorf("%w: chunk row count does not match column length", arrow.ErrInvalid)
+ }
+
+ validityNulls := chunksHaveNulls(chunks)
+ typeID := chunks[0].DataType().ID()
+ switch typeID {
+ case arrow.INT8:
+ return newPhysicalSortInt8Column(chunks, numRows, validityNulls), nil
+ case arrow.INT16:
+ return newPhysicalSortInt16Column(chunks, numRows, validityNulls), nil
+ case arrow.INT32:
+ return newPhysicalSortInt32Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE32:
+ return newPhysicalSortDate32Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME32:
+ return newPhysicalSortTime32Column(chunks, numRows, validityNulls), nil
+ case arrow.INT64:
+ return newPhysicalSortInt64Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE64:
+ return newPhysicalSortDate64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME64:
+ return newPhysicalSortTime64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIMESTAMP:
+ return newPhysicalSortTimestampColumn(chunks, numRows, validityNulls), nil
+ case arrow.DURATION:
+ return newPhysicalSortDurationColumn(chunks, numRows, validityNulls), nil
+ case arrow.UINT8:
+ return newPhysicalSortUint8Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT16:
+ return newPhysicalSortUint16Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT32:
+ return newPhysicalSortUint32Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT64:
+ return newPhysicalSortUint64Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT16:
+ return newPhysicalSortFloat16Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT32:
+ return newPhysicalSortFloat32Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT64:
+ return newPhysicalSortFloat64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL32:
+ return newPhysicalSortDecimal32Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL64:
+ return newPhysicalSortDecimal64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL128:
+ return newPhysicalSortDecimal128Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL256:
+ return newPhysicalSortDecimal256Column(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTHS:
+ return newPhysicalSortMonthIntervalColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_DAY_TIME:
+ return newPhysicalSortDayTimeColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTH_DAY_NANO:
+ return newPhysicalSortMonthDayNanoColumn(chunks, numRows, validityNulls), nil
+ case arrow.BOOL:
+ return newPhysicalSortBoolColumn(chunks, numRows, validityNulls), nil
+ case arrow.STRING:
+ return newPhysicalSortStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_STRING:
+ return newPhysicalSortLargeStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.BINARY:
+ return newPhysicalSortBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_BINARY:
+ return newPhysicalSortLargeBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.FIXED_SIZE_BINARY:
+ return newFixedSizeBinaryComparator(chunks, numRows, validityNulls)
+ case arrow.EXTENSION:
+ storageChunks, err := extensionStorageFixedSizeBinaryChunks(chunks)
+ if err != nil {
+ return nil, err
+ }
+ return newFixedSizeBinaryComparator(storageChunks, numRows, validityNulls)
+ default:
+ return nil, fmt.Errorf("%w: sorting not supported for type %s", arrow.ErrNotImplemented, typeID)
+ }
+}
+
+// chunkIndexSpan represents a contiguous range of indices in the global order.
+type chunkIndexSpan struct {
+ lo, hi int
+}
+
+// mergeAdjacentStable merges sorted adjacent ranges [a0,a1) and [b0,b1) (a1 == b0) into indices[lo:hi]
+// using a strict weak order: i is ordered before j iff less(i,j). Tie-breaking prefers the left range
+// (stable merge, same as C++ std::merge with !comp(right,left)).
+func mergeAdjacentStable(indices, tmp []uint64, a0, a1, b0, b1 int, less func(a, b uint64) bool) {
+ i, j, k := a0, b0, a0
+ for i < a1 && j < b1 {
+ if !less(indices[j], indices[i]) {
+ tmp[k] = indices[i]
+ i++
+ } else {
+ tmp[k] = indices[j]
+ j++
+ }
+ k++
+ }
+ for i < a1 {
+ tmp[k] = indices[i]
+ k++
+ i++
+ }
+ for j < b1 {
+ tmp[k] = indices[j]
+ k++
+ j++
+ }
+ copy(indices[a0:b1], tmp[a0:b1])
+}
+
+// pairwiseMergeSortedSpans merges already-sorted adjacent index spans (chunk batch rows in global
+// order), matching Arrow C++ ChunkedMergeImpl / TableSorter batch merge (vector_sort.cc).
+// spanScratch must have capacity >= len(spans); it ping-pongs with spans' backing during merging.
+func pairwiseMergeSortedSpans(indices, tmp []uint64, spans []chunkIndexSpan, less func(a, b uint64) bool, spanScratch []chunkIndexSpan) {
+ if len(spans) <= 1 {
+ return
+ }
+ if cap(spanScratch) < len(spans) {
+ panic("kernels: spanScratch cap < len(spans)")
+ }
+ cur := spans
+ other := spanScratch[:0]
+ for len(cur) > 1 {
+ other = other[:0]
+ for i := 0; i < len(cur); i += 2 {
+ if i+1 < len(cur) {
+ s0, s1 := cur[i], cur[i+1]
+ mergeAdjacentStable(indices, tmp, s0.lo, s0.hi, s1.lo, s1.hi, less)
+ other = append(other, chunkIndexSpan{s0.lo, s1.hi})
+ } else {
+ other = append(other, cur[i])
+ }
+ }
+ cur, other = other, cur
+ }
+}
+
+// alignedChunkBoundaries reports cumulative row offsets for chunk boundaries when every sort column
+// has the same chunk count and matching chunk lengths (typical for Arrow tables).
+func alignedChunkBoundaries(columns []*arrow.Chunked) ([]int, bool) {
+ if len(columns) == 0 {
+ return nil, false
+ }
+ ch0 := columns[0].Chunks()
+ n := len(ch0)
+ if n == 0 {
+ return nil, false
+ }
+ offs := make([]int, n+1)
+ for i := 0; i < n; i++ {
+ L := ch0[i].Len()
Review Comment:
please pick a better variable name than just `L`
##########
arrow/compute/internal/kernels/vector_sort.go:
##########
@@ -0,0 +1,476 @@
+// 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.
+
+//go:build go1.18
+
+package kernels
+
+import (
+ "fmt"
+ "slices"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/compute/exec"
+)
+
+// SortOrder specifies the sort order for sorting operations.
+type SortOrder int8
+
+const (
+ Ascending SortOrder = iota
+ Descending
+)
+
+// NullPlacement specifies where null values should be placed in the sort order.
+type NullPlacement int8
+
+const (
+ NullsAtEnd NullPlacement = iota
+ NullsAtStart
+)
+
+// SortOptions defines options for the sort_indices function.
+type SortOptions struct {
+ Order SortOrder `compute:"order"`
+ NullPlacement NullPlacement `compute:"null_placement"`
+}
+
+func (SortOptions) TypeName() string { return "SortOptions" }
+
+type SortState = SortOptions
+
+// SortKey defines a column to sort by with its ordering and null placement options.
+type SortKey struct {
+ ColumnIndex int
+ Order SortOrder
+ NullPlacement NullPlacement
+}
+
+// Chunk-aware sort_indices: logical row IDs 0..n-1, no chunk concatenation. Structure follows
+// Apache Arrow C++ vector_sort.cc / vector_sort_internal.h (see vector_sort_internal.go).
+//
+// Per-column data uses a dense logicalRowMap for O(1) chunk resolution under random compares.
+// Each sortable physical type has a dedicated comparator struct in vector_sort_physical.go (C++
+// ConcreteColumnComparator<T> shape): full monomorphization for the hot compare path; no
+// value-level compare func pointer.
+// compareRowsForKey implements the same ordering as C++ (null placement, NaN, Order).
+//
+// Single key: ChunkedArraySorter — arraySortOneColumnRange per chunk (PartitionNullsOnly /
+// PartitionNullLikes + stable_sort finites), then pairwise merge (ChunkedMergeImpl-style merge
+// using full row order; C++ splits null / non-null merge when the type has null-likes).
+//
+// Multi-key, aligned chunks: TableSorter — per-chunk RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter, then merge.
+//
+// Multi-key, single segment: RadixRecordBatchSorter (<= maxRadixSortKeys) or
+// MultipleKeyRecordBatchSorter (> maxRadixSortKeys).
+
+// maxRadixSortKeys matches Arrow C++ kMaxRadixSortKeys (vector_sort.cc): above this, one global
+// multi-key stable sort is used instead of MSD radix.
+const maxRadixSortKeys = 8
+
+// columnComparator is the Go analogue of compute::internal::ColumnComparator (vector_sort_internal.h):
+// per-column row compare + null / null-like metadata for partitioning.
+type columnComparator interface {
+ // compareRowsForKey returns -1 if i before j, +1 if i after j, 0 if tied on this column
+ // (both null, or both non-null and equal), so the caller may advance to the next sort key.
+ compareRowsForKey(i, j uint64, key SortKey) int
+ // isNullAt returns true if the global row index is null.
+ isNullAt(global uint64) bool
+ // hasNullLikeValues returns true if the column has null-like values.
+ hasNullLikeValues() bool
+ // isNullLikeAt returns true if the global row index is a null-like value.
+ isNullLikeAt(global uint64) bool
+ // columnHasValidityNulls mirrors Array::null_count() != 0; when false, C++ skips PartitionNullsOnly.
+ columnHasValidityNulls() bool
+}
+
+// multiColumnComparator compares two logical rows (global uint64 indices) lexicographically
+// across every sort key. That matches C++ MultipleKeyComparator::CompareInternal(left, right, 0)
+// (vector_sort_internal.h), but it is not a port of the whole MultipleKeyComparator type: C++ keeps
+// ResolvedSortKey per column, uses Location (int64 batch row vs ChunkLocation on tables), builds
+// virtual ColumnComparator instances, and passes start_sort_key_index for radix tails and other
+// partial key ranges — in Go those suffix compares are makeTailComparator(comparators, keys, from).
+type multiColumnComparator struct {
+ columns []columnComparator
+ keys []SortKey
+}
+
+// compare is a three-way ordering for stable sort / merge: negative if idxA before idxB, etc.
+func (m *multiColumnComparator) compare(idxA, idxB uint64) int {
+ for i, key := range m.keys {
+ if cmpVal := m.columns[i].compareRowsForKey(idxA, idxB, key); cmpVal != 0 {
+ return cmpVal
+ }
+ }
+ return 0
+}
+
+func extensionStorageFixedSizeBinaryChunks(chunks []arrow.Array) ([]arrow.Array, error) {
+ out := make([]arrow.Array, len(chunks))
+ for i, ch := range chunks {
+ ext, ok := ch.(array.ExtensionArray)
+ if !ok {
+ return nil, fmt.Errorf("%w: extension column must implement array.ExtensionArray", arrow.ErrInvalid)
+ }
+ st := ext.Storage()
+ if st.DataType().ID() != arrow.FIXED_SIZE_BINARY {
+ return nil, fmt.Errorf("%w: sorting extension columns is only supported when storage is fixed_size_binary (got %s)",
+ arrow.ErrNotImplemented, st.DataType())
+ }
+ out[i] = st
+ }
+ return out, nil
+}
+
+func newFixedSizeBinaryComparator(chunks []arrow.Array, numRows int, vn bool) (columnComparator, error) {
+ f0, ok := chunks[0].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ w := f0.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ for i := 1; i < len(chunks); i++ {
+ fi, ok := chunks[i].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ wi := fi.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ if wi != w {
+ return nil, fmt.Errorf("%w: fixed_size_binary chunks must have the same byte width (%d vs %d)",
+ arrow.ErrInvalid, w, wi)
+ }
+ }
+ return newPhysicalSortFixedSizeBinaryColumn(chunks, numRows, vn), nil
+}
+
+// createChunkedComparator builds a column comparator for these chunks (one Arrow type for all chunks).
+func createChunkedComparator(chunks []arrow.Array, numRows int) (columnComparator, error) {
+ if len(chunks) == 0 {
+ return nil, fmt.Errorf("%w: cannot create comparator for empty chunk list", arrow.ErrInvalid)
+ }
+ if totalChunkRows(chunks) != numRows {
+ return nil, fmt.Errorf("%w: chunk row count does not match column length", arrow.ErrInvalid)
+ }
+
+ validityNulls := chunksHaveNulls(chunks)
+ typeID := chunks[0].DataType().ID()
+ switch typeID {
+ case arrow.INT8:
+ return newPhysicalSortInt8Column(chunks, numRows, validityNulls), nil
+ case arrow.INT16:
+ return newPhysicalSortInt16Column(chunks, numRows, validityNulls), nil
+ case arrow.INT32:
+ return newPhysicalSortInt32Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE32:
+ return newPhysicalSortDate32Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME32:
+ return newPhysicalSortTime32Column(chunks, numRows, validityNulls), nil
+ case arrow.INT64:
+ return newPhysicalSortInt64Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE64:
+ return newPhysicalSortDate64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME64:
+ return newPhysicalSortTime64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIMESTAMP:
+ return newPhysicalSortTimestampColumn(chunks, numRows, validityNulls), nil
+ case arrow.DURATION:
+ return newPhysicalSortDurationColumn(chunks, numRows, validityNulls), nil
+ case arrow.UINT8:
+ return newPhysicalSortUint8Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT16:
+ return newPhysicalSortUint16Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT32:
+ return newPhysicalSortUint32Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT64:
+ return newPhysicalSortUint64Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT16:
+ return newPhysicalSortFloat16Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT32:
+ return newPhysicalSortFloat32Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT64:
+ return newPhysicalSortFloat64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL32:
+ return newPhysicalSortDecimal32Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL64:
+ return newPhysicalSortDecimal64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL128:
+ return newPhysicalSortDecimal128Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL256:
+ return newPhysicalSortDecimal256Column(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTHS:
+ return newPhysicalSortMonthIntervalColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_DAY_TIME:
+ return newPhysicalSortDayTimeColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTH_DAY_NANO:
+ return newPhysicalSortMonthDayNanoColumn(chunks, numRows, validityNulls), nil
+ case arrow.BOOL:
+ return newPhysicalSortBoolColumn(chunks, numRows, validityNulls), nil
+ case arrow.STRING:
+ return newPhysicalSortStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_STRING:
+ return newPhysicalSortLargeStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.BINARY:
+ return newPhysicalSortBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_BINARY:
+ return newPhysicalSortLargeBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.FIXED_SIZE_BINARY:
+ return newFixedSizeBinaryComparator(chunks, numRows, validityNulls)
+ case arrow.EXTENSION:
+ storageChunks, err := extensionStorageFixedSizeBinaryChunks(chunks)
+ if err != nil {
+ return nil, err
+ }
+ return newFixedSizeBinaryComparator(storageChunks, numRows, validityNulls)
+ default:
+ return nil, fmt.Errorf("%w: sorting not supported for type %s", arrow.ErrNotImplemented, typeID)
+ }
+}
+
+// chunkIndexSpan represents a contiguous range of indices in the global order.
+type chunkIndexSpan struct {
+ lo, hi int
+}
+
+// mergeAdjacentStable merges sorted adjacent ranges [a0,a1) and [b0,b1) (a1 == b0) into indices[lo:hi]
+// using a strict weak order: i is ordered before j iff less(i,j). Tie-breaking prefers the left range
+// (stable merge, same as C++ std::merge with !comp(right,left)).
+func mergeAdjacentStable(indices, tmp []uint64, a0, a1, b0, b1 int, less func(a, b uint64) bool) {
+ i, j, k := a0, b0, a0
+ for i < a1 && j < b1 {
+ if !less(indices[j], indices[i]) {
+ tmp[k] = indices[i]
+ i++
+ } else {
+ tmp[k] = indices[j]
+ j++
+ }
+ k++
+ }
+ for i < a1 {
+ tmp[k] = indices[i]
+ k++
+ i++
+ }
+ for j < b1 {
+ tmp[k] = indices[j]
+ k++
+ j++
+ }
+ copy(indices[a0:b1], tmp[a0:b1])
+}
+
+// pairwiseMergeSortedSpans merges already-sorted adjacent index spans (chunk batch rows in global
+// order), matching Arrow C++ ChunkedMergeImpl / TableSorter batch merge (vector_sort.cc).
+// spanScratch must have capacity >= len(spans); it ping-pongs with spans' backing during merging.
+func pairwiseMergeSortedSpans(indices, tmp []uint64, spans []chunkIndexSpan, less func(a, b uint64) bool, spanScratch []chunkIndexSpan) {
+ if len(spans) <= 1 {
+ return
+ }
+ if cap(spanScratch) < len(spans) {
+ panic("kernels: spanScratch cap < len(spans)")
+ }
+ cur := spans
+ other := spanScratch[:0]
+ for len(cur) > 1 {
+ other = other[:0]
+ for i := 0; i < len(cur); i += 2 {
+ if i+1 < len(cur) {
+ s0, s1 := cur[i], cur[i+1]
+ mergeAdjacentStable(indices, tmp, s0.lo, s0.hi, s1.lo, s1.hi, less)
+ other = append(other, chunkIndexSpan{s0.lo, s1.hi})
+ } else {
+ other = append(other, cur[i])
+ }
+ }
+ cur, other = other, cur
+ }
+}
+
+// alignedChunkBoundaries reports cumulative row offsets for chunk boundaries when every sort column
+// has the same chunk count and matching chunk lengths (typical for Arrow tables).
+func alignedChunkBoundaries(columns []*arrow.Chunked) ([]int, bool) {
+ if len(columns) == 0 {
+ return nil, false
+ }
+ ch0 := columns[0].Chunks()
+ n := len(ch0)
+ if n == 0 {
+ return nil, false
+ }
+ offs := make([]int, n+1)
+ for i := 0; i < n; i++ {
+ L := ch0[i].Len()
+ for j := 1; j < len(columns); j++ {
+ cj := columns[j].Chunks()
+ if len(cj) != n || cj[i].Len() != L {
+ return nil, false
+ }
+ }
+ offs[i+1] = offs[i] + L
+ }
+ if offs[n] != columns[0].Len() {
+ return nil, false
+ }
+ return offs, true
+}
+
+// sortIndicesSingleColumnChunked implements Arrow C++ ChunkedArraySorter for one logical column:
+// per-chunk array sort (partition + sort finites), then pairwise merge (ChunkedMergeImpl).
+func sortIndicesSingleColumnChunked(indices []uint64, chunks []arrow.Array, comp columnComparator, key SortKey, tmp []uint64, spanScratch []chunkIndexSpan) {
+ lo := 0
+ for _, ch := range chunks {
+ hi := lo + ch.Len()
+ arraySortOneColumnRange(indices, tmp, comp, key, lo, hi)
+ lo = hi
+ }
+
+ nChunks := len(chunks)
+ if nChunks <= 1 {
+ return
+ }
+
+ less := func(a, b uint64) bool { return comp.compareRowsForKey(a, b, key) < 0 }
+
+ spans := make([]chunkIndexSpan, nChunks)
+ lo = 0
+ for i, ch := range chunks {
+ hi := lo + ch.Len()
+ spans[i] = chunkIndexSpan{lo, hi}
+ lo = hi
+ }
+ pairwiseMergeSortedSpans(indices, tmp, spans, less, spanScratch)
+}
+
+// sortIndicesMultiColumnAlignedChunks sorts each aligned chunk (C++ RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter), then merges like Arrow C++ TableSorter.
+func sortIndicesMultiColumnAlignedChunks(indices []uint64, offs []int, comparators []columnComparator, keys []SortKey, multiComp *multiColumnComparator, tmp []uint64, spanScratch []chunkIndexSpan) {
+ nChunks := len(offs) - 1
+ useRadix := len(keys) <= maxRadixSortKeys
+ for c := 0; c < nChunks; c++ {
+ lo, hi := offs[c], offs[c+1]
+ if useRadix {
+ radixRecordBatchSortRange(indices, tmp, comparators, keys, 0, lo, hi)
+ } else {
+ multipleKeyRecordBatchSortRange(indices, tmp, comparators, keys, lo, hi, makeTailComparator(comparators, keys, 1))
+ }
+ }
+ if nChunks <= 1 {
+ return
+ }
+ less := func(a, b uint64) bool { return multiComp.compare(a, b) < 0 }
+ spans := make([]chunkIndexSpan, nChunks)
+ for c := 0; c < nChunks; c++ {
Review Comment:
```suggestion
for c := range nChunks {
```
##########
arrow/compute/internal/kernels/vector_sort.go:
##########
@@ -0,0 +1,476 @@
+// 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.
+
+//go:build go1.18
+
+package kernels
+
+import (
+ "fmt"
+ "slices"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/compute/exec"
+)
+
+// SortOrder specifies the sort order for sorting operations.
+type SortOrder int8
+
+const (
+ Ascending SortOrder = iota
+ Descending
+)
+
+// NullPlacement specifies where null values should be placed in the sort order.
+type NullPlacement int8
+
+const (
+ NullsAtEnd NullPlacement = iota
+ NullsAtStart
+)
+
+// SortOptions defines options for the sort_indices function.
+type SortOptions struct {
+ Order SortOrder `compute:"order"`
+ NullPlacement NullPlacement `compute:"null_placement"`
+}
+
+func (SortOptions) TypeName() string { return "SortOptions" }
+
+type SortState = SortOptions
+
+// SortKey defines a column to sort by with its ordering and null placement options.
+type SortKey struct {
+ ColumnIndex int
+ Order SortOrder
+ NullPlacement NullPlacement
+}
+
+// Chunk-aware sort_indices: logical row IDs 0..n-1, no chunk concatenation. Structure follows
+// Apache Arrow C++ vector_sort.cc / vector_sort_internal.h (see vector_sort_internal.go).
+//
+// Per-column data uses a dense logicalRowMap for O(1) chunk resolution under random compares.
+// Each sortable physical type has a dedicated comparator struct in vector_sort_physical.go (C++
+// ConcreteColumnComparator<T> shape): full monomorphization for the hot compare path; no
+// value-level compare func pointer.
+// compareRowsForKey implements the same ordering as C++ (null placement, NaN, Order).
+//
+// Single key: ChunkedArraySorter — arraySortOneColumnRange per chunk (PartitionNullsOnly /
+// PartitionNullLikes + stable_sort finites), then pairwise merge (ChunkedMergeImpl-style merge
+// using full row order; C++ splits null / non-null merge when the type has null-likes).
+//
+// Multi-key, aligned chunks: TableSorter — per-chunk RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter, then merge.
+//
+// Multi-key, single segment: RadixRecordBatchSorter (<= maxRadixSortKeys) or
+// MultipleKeyRecordBatchSorter (> maxRadixSortKeys).
+
+// maxRadixSortKeys matches Arrow C++ kMaxRadixSortKeys (vector_sort.cc): above this, one global
+// multi-key stable sort is used instead of MSD radix.
+const maxRadixSortKeys = 8
+
+// columnComparator is the Go analogue of compute::internal::ColumnComparator (vector_sort_internal.h):
+// per-column row compare + null / null-like metadata for partitioning.
+type columnComparator interface {
+ // compareRowsForKey returns -1 if i before j, +1 if i after j, 0 if tied on this column
+ // (both null, or both non-null and equal), so the caller may advance to the next sort key.
+ compareRowsForKey(i, j uint64, key SortKey) int
+ // isNullAt returns true if the global row index is null.
+ isNullAt(global uint64) bool
+ // hasNullLikeValues returns true if the column has null-like values.
+ hasNullLikeValues() bool
+ // isNullLikeAt returns true if the global row index is a null-like value.
+ isNullLikeAt(global uint64) bool
+ // columnHasValidityNulls mirrors Array::null_count() != 0; when false, C++ skips PartitionNullsOnly.
+ columnHasValidityNulls() bool
+}
+
+// multiColumnComparator compares two logical rows (global uint64 indices) lexicographically
+// across every sort key. That matches C++ MultipleKeyComparator::CompareInternal(left, right, 0)
+// (vector_sort_internal.h), but it is not a port of the whole MultipleKeyComparator type: C++ keeps
+// ResolvedSortKey per column, uses Location (int64 batch row vs ChunkLocation on tables), builds
+// virtual ColumnComparator instances, and passes start_sort_key_index for radix tails and other
+// partial key ranges — in Go those suffix compares are makeTailComparator(comparators, keys, from).
+type multiColumnComparator struct {
+ columns []columnComparator
+ keys []SortKey
+}
+
+// compare is a three-way ordering for stable sort / merge: negative if idxA before idxB, etc.
+func (m *multiColumnComparator) compare(idxA, idxB uint64) int {
+ for i, key := range m.keys {
+ if cmpVal := m.columns[i].compareRowsForKey(idxA, idxB, key); cmpVal != 0 {
+ return cmpVal
+ }
+ }
+ return 0
+}
+
+func extensionStorageFixedSizeBinaryChunks(chunks []arrow.Array) ([]arrow.Array, error) {
+ out := make([]arrow.Array, len(chunks))
+ for i, ch := range chunks {
+ ext, ok := ch.(array.ExtensionArray)
+ if !ok {
+ return nil, fmt.Errorf("%w: extension column must implement array.ExtensionArray", arrow.ErrInvalid)
+ }
+ st := ext.Storage()
+ if st.DataType().ID() != arrow.FIXED_SIZE_BINARY {
+ return nil, fmt.Errorf("%w: sorting extension columns is only supported when storage is fixed_size_binary (got %s)",
+ arrow.ErrNotImplemented, st.DataType())
+ }
+ out[i] = st
+ }
+ return out, nil
+}
+
+func newFixedSizeBinaryComparator(chunks []arrow.Array, numRows int, vn bool) (columnComparator, error) {
+ f0, ok := chunks[0].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ w := f0.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ for i := 1; i < len(chunks); i++ {
+ fi, ok := chunks[i].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ wi := fi.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ if wi != w {
+ return nil, fmt.Errorf("%w: fixed_size_binary chunks must have the same byte width (%d vs %d)",
+ arrow.ErrInvalid, w, wi)
+ }
+ }
+ return newPhysicalSortFixedSizeBinaryColumn(chunks, numRows, vn), nil
+}
+
+// createChunkedComparator builds a column comparator for these chunks (one Arrow type for all chunks).
+func createChunkedComparator(chunks []arrow.Array, numRows int) (columnComparator, error) {
+ if len(chunks) == 0 {
+ return nil, fmt.Errorf("%w: cannot create comparator for empty chunk list", arrow.ErrInvalid)
+ }
+ if totalChunkRows(chunks) != numRows {
+ return nil, fmt.Errorf("%w: chunk row count does not match column length", arrow.ErrInvalid)
+ }
+
+ validityNulls := chunksHaveNulls(chunks)
+ typeID := chunks[0].DataType().ID()
+ switch typeID {
+ case arrow.INT8:
+ return newPhysicalSortInt8Column(chunks, numRows, validityNulls), nil
+ case arrow.INT16:
+ return newPhysicalSortInt16Column(chunks, numRows, validityNulls), nil
+ case arrow.INT32:
+ return newPhysicalSortInt32Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE32:
+ return newPhysicalSortDate32Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME32:
+ return newPhysicalSortTime32Column(chunks, numRows, validityNulls), nil
+ case arrow.INT64:
+ return newPhysicalSortInt64Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE64:
+ return newPhysicalSortDate64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME64:
+ return newPhysicalSortTime64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIMESTAMP:
+ return newPhysicalSortTimestampColumn(chunks, numRows, validityNulls), nil
+ case arrow.DURATION:
+ return newPhysicalSortDurationColumn(chunks, numRows, validityNulls), nil
+ case arrow.UINT8:
+ return newPhysicalSortUint8Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT16:
+ return newPhysicalSortUint16Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT32:
+ return newPhysicalSortUint32Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT64:
+ return newPhysicalSortUint64Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT16:
+ return newPhysicalSortFloat16Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT32:
+ return newPhysicalSortFloat32Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT64:
+ return newPhysicalSortFloat64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL32:
+ return newPhysicalSortDecimal32Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL64:
+ return newPhysicalSortDecimal64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL128:
+ return newPhysicalSortDecimal128Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL256:
+ return newPhysicalSortDecimal256Column(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTHS:
+ return newPhysicalSortMonthIntervalColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_DAY_TIME:
+ return newPhysicalSortDayTimeColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTH_DAY_NANO:
+ return newPhysicalSortMonthDayNanoColumn(chunks, numRows, validityNulls), nil
+ case arrow.BOOL:
+ return newPhysicalSortBoolColumn(chunks, numRows, validityNulls), nil
+ case arrow.STRING:
+ return newPhysicalSortStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_STRING:
+ return newPhysicalSortLargeStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.BINARY:
+ return newPhysicalSortBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_BINARY:
+ return newPhysicalSortLargeBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.FIXED_SIZE_BINARY:
+ return newFixedSizeBinaryComparator(chunks, numRows, validityNulls)
+ case arrow.EXTENSION:
+ storageChunks, err := extensionStorageFixedSizeBinaryChunks(chunks)
+ if err != nil {
+ return nil, err
+ }
+ return newFixedSizeBinaryComparator(storageChunks, numRows, validityNulls)
+ default:
+ return nil, fmt.Errorf("%w: sorting not supported for type %s", arrow.ErrNotImplemented, typeID)
+ }
+}
+
+// chunkIndexSpan represents a contiguous range of indices in the global order.
+type chunkIndexSpan struct {
+ lo, hi int
+}
+
+// mergeAdjacentStable merges sorted adjacent ranges [a0,a1) and [b0,b1) (a1 == b0) into indices[lo:hi]
+// using a strict weak order: i is ordered before j iff less(i,j). Tie-breaking prefers the left range
+// (stable merge, same as C++ std::merge with !comp(right,left)).
+func mergeAdjacentStable(indices, tmp []uint64, a0, a1, b0, b1 int, less func(a, b uint64) bool) {
+ i, j, k := a0, b0, a0
+ for i < a1 && j < b1 {
+ if !less(indices[j], indices[i]) {
+ tmp[k] = indices[i]
+ i++
+ } else {
+ tmp[k] = indices[j]
+ j++
+ }
+ k++
+ }
+ for i < a1 {
+ tmp[k] = indices[i]
+ k++
+ i++
+ }
+ for j < b1 {
+ tmp[k] = indices[j]
+ k++
+ j++
+ }
+ copy(indices[a0:b1], tmp[a0:b1])
+}
+
+// pairwiseMergeSortedSpans merges already-sorted adjacent index spans (chunk batch rows in global
+// order), matching Arrow C++ ChunkedMergeImpl / TableSorter batch merge (vector_sort.cc).
+// spanScratch must have capacity >= len(spans); it ping-pongs with spans' backing during merging.
+func pairwiseMergeSortedSpans(indices, tmp []uint64, spans []chunkIndexSpan, less func(a, b uint64) bool, spanScratch []chunkIndexSpan) {
+ if len(spans) <= 1 {
+ return
+ }
+ if cap(spanScratch) < len(spans) {
+ panic("kernels: spanScratch cap < len(spans)")
+ }
+ cur := spans
+ other := spanScratch[:0]
+ for len(cur) > 1 {
+ other = other[:0]
+ for i := 0; i < len(cur); i += 2 {
+ if i+1 < len(cur) {
+ s0, s1 := cur[i], cur[i+1]
+ mergeAdjacentStable(indices, tmp, s0.lo, s0.hi, s1.lo, s1.hi, less)
+ other = append(other, chunkIndexSpan{s0.lo, s1.hi})
+ } else {
+ other = append(other, cur[i])
+ }
+ }
+ cur, other = other, cur
+ }
+}
+
+// alignedChunkBoundaries reports cumulative row offsets for chunk boundaries when every sort column
+// has the same chunk count and matching chunk lengths (typical for Arrow tables).
+func alignedChunkBoundaries(columns []*arrow.Chunked) ([]int, bool) {
+ if len(columns) == 0 {
+ return nil, false
+ }
+ ch0 := columns[0].Chunks()
+ n := len(ch0)
+ if n == 0 {
+ return nil, false
+ }
+ offs := make([]int, n+1)
+ for i := 0; i < n; i++ {
+ L := ch0[i].Len()
+ for j := 1; j < len(columns); j++ {
+ cj := columns[j].Chunks()
+ if len(cj) != n || cj[i].Len() != L {
+ return nil, false
+ }
+ }
+ offs[i+1] = offs[i] + L
+ }
+ if offs[n] != columns[0].Len() {
+ return nil, false
+ }
+ return offs, true
+}
+
+// sortIndicesSingleColumnChunked implements Arrow C++ ChunkedArraySorter for one logical column:
+// per-chunk array sort (partition + sort finites), then pairwise merge (ChunkedMergeImpl).
+func sortIndicesSingleColumnChunked(indices []uint64, chunks []arrow.Array, comp columnComparator, key SortKey, tmp []uint64, spanScratch []chunkIndexSpan) {
+ lo := 0
+ for _, ch := range chunks {
+ hi := lo + ch.Len()
+ arraySortOneColumnRange(indices, tmp, comp, key, lo, hi)
+ lo = hi
+ }
+
+ nChunks := len(chunks)
+ if nChunks <= 1 {
+ return
+ }
+
+ less := func(a, b uint64) bool { return comp.compareRowsForKey(a, b, key) < 0 }
+
+ spans := make([]chunkIndexSpan, nChunks)
+ lo = 0
+ for i, ch := range chunks {
+ hi := lo + ch.Len()
+ spans[i] = chunkIndexSpan{lo, hi}
+ lo = hi
+ }
+ pairwiseMergeSortedSpans(indices, tmp, spans, less, spanScratch)
+}
+
+// sortIndicesMultiColumnAlignedChunks sorts each aligned chunk (C++ RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter), then merges like Arrow C++ TableSorter.
+func sortIndicesMultiColumnAlignedChunks(indices []uint64, offs []int, comparators []columnComparator, keys []SortKey, multiComp *multiColumnComparator, tmp []uint64, spanScratch []chunkIndexSpan) {
+ nChunks := len(offs) - 1
+ useRadix := len(keys) <= maxRadixSortKeys
+ for c := 0; c < nChunks; c++ {
+ lo, hi := offs[c], offs[c+1]
+ if useRadix {
+ radixRecordBatchSortRange(indices, tmp, comparators, keys, 0, lo, hi)
+ } else {
+ multipleKeyRecordBatchSortRange(indices, tmp, comparators, keys, lo, hi, makeTailComparator(comparators, keys, 1))
+ }
+ }
+ if nChunks <= 1 {
+ return
+ }
+ less := func(a, b uint64) bool { return multiComp.compare(a, b) < 0 }
+ spans := make([]chunkIndexSpan, nChunks)
+ for c := 0; c < nChunks; c++ {
+ spans[c] = chunkIndexSpan{offs[c], offs[c+1]}
+ }
+ pairwiseMergeSortedSpans(indices, tmp, spans, less, spanScratch)
+}
+
+// SortIndices returns a stable permutation of 0..n-1 that would lexicographically sort the given
+// columns. Each *arrow.Chunked is used via its .Chunks() only—no concatenate. columns[i] pairs with
+// keys[i] for order and null placement on that column.
+func SortIndices(ctx *exec.KernelCtx, columns []*arrow.Chunked, keys []SortKey) (*exec.ExecResult, error) {
+ if len(columns) == 0 || len(keys) == 0 {
+ return nil, fmt.Errorf("%w: must have at least one column and one sort key", arrow.ErrInvalid)
+ }
+
+ if len(columns) != len(keys) {
+ return nil, fmt.Errorf("%w: number of columns (%d) must match number of sort keys (%d)",
+ arrow.ErrInvalid, len(columns), len(keys))
+ }
+
+ length := int64(columns[0].Len())
+ for _, col := range columns {
+ if int64(col.Len()) != length {
+ return nil, fmt.Errorf("%w: all columns must have the same length", arrow.ErrInvalid)
+ }
+ }
+
+ comparators := make([]columnComparator, len(columns))
+ nRows := int(length)
+ for i, col := range columns {
+ comp, err := createChunkedComparator(col.Chunks(), nRows)
+ if err != nil {
+ return nil, err
+ }
+ comparators[i] = comp
+ }
+
+ multiComp := &multiColumnComparator{
+ columns: comparators,
+ keys: keys,
+ }
+
+ out := &exec.ExecResult{}
+ out.Len = length
+ out.Type = arrow.PrimitiveTypes.Uint64
+ out.Nulls = 0
+
+ buf := ctx.Allocate(int(length) * arrow.Uint64SizeBytes)
+ indices := arrow.Uint64Traits.CastFromBytes(buf.Buf())[:length]
+
+ for i := range indices {
+ indices[i] = uint64(i)
+ }
+
+ if len(keys) == 1 {
+ chunks := columns[0].Chunks()
Review Comment:
shouldn't this use keys[0].ColumnIndex instead of 0?
##########
arrow/compute/internal/kernels/vector_sort_internal.go:
##########
@@ -0,0 +1,280 @@
+// 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.
+
+//go:build go1.18
+
+package kernels
+
+import (
+ "slices"
+)
+
+// Ported from Apache Arrow C++ vector_sort_internal.h / vector_sort.cc:
+// GenericNullPartitionResult, PartitionNullsOnly, PartitionNullLikes, VisitConstantRanges,
+// ConcreteRecordBatchColumnSorter::SortRange (radix / column-wise multi-key path).
+
+// nullPartitionIndices holds inclusive-exclusive offsets into the indices buffer (like uint64_t*
+// ranges in C++ GenericNullPartitionResult).
+type nullPartitionIndices struct {
+ nonNullsLo, nonNullsHi int
+ nullsLo, nullsHi int
+}
+
+// partitionNullsOnly mirrors PartitionNullsOnly<StablePartitioner> in vector_sort_internal.h.
+func partitionNullsOnly(indices, scratch []uint64, lo, hi int, nullPlacement NullPlacement, isNull func(uint64) bool) nullPartitionIndices {
+ if lo >= hi {
+ return nullPartitionIndices{lo, lo, lo, lo}
+ }
+ hasNull := false
+ for i := lo; i < hi; i++ {
+ if isNull(indices[i]) {
+ hasNull = true
+ break
+ }
+ }
+ if !hasNull {
+ if nullPlacement == NullsAtStart {
+ return nullPartitionIndices{lo, hi, lo, lo}
+ }
+ return nullPartitionIndices{lo, hi, hi, hi}
+ }
+ if nullPlacement == NullsAtStart {
+ t := 0
+ for i := lo; i < hi; i++ {
+ if isNull(indices[i]) {
+ scratch[lo+t] = indices[i]
+ t++
+ }
+ }
+ nullEnd := lo + t
+ u := t
+ for i := lo; i < hi; i++ {
+ if !isNull(indices[i]) {
+ scratch[lo+u] = indices[i]
+ u++
+ }
+ }
+ copy(indices[lo:hi], scratch[lo:hi])
+ return nullPartitionIndices{nullEnd, hi, lo, nullEnd}
+ }
+ t := 0
+ for i := lo; i < hi; i++ {
+ if !isNull(indices[i]) {
+ scratch[lo+t] = indices[i]
+ t++
+ }
+ }
+ nnEnd := lo + t
+ u := t
+ for i := lo; i < hi; i++ {
+ if isNull(indices[i]) {
+ scratch[lo+u] = indices[i]
+ u++
+ }
+ }
+ copy(indices[lo:hi], scratch[lo:hi])
+ return nullPartitionIndices{lo, nnEnd, nnEnd, hi}
+}
+
+// partitionNullLikes mirrors PartitionNullLikes in vector_sort_internal.h (NaN for floats).
+func partitionNullLikes(indices, scratch []uint64, lo, hi int, nullPlacement NullPlacement, hasNullLike bool, isNullLike func(uint64) bool) nullPartitionIndices {
+ if !hasNullLike || lo >= hi {
+ if nullPlacement == NullsAtStart {
+ return nullPartitionIndices{lo, hi, lo, lo}
+ }
+ return nullPartitionIndices{lo, hi, hi, hi}
+ }
+ hasLike := false
+ for i := lo; i < hi; i++ {
+ if isNullLike(indices[i]) {
+ hasLike = true
+ break
+ }
+ }
+ if !hasLike {
+ if nullPlacement == NullsAtStart {
+ return nullPartitionIndices{lo, hi, lo, lo}
+ }
+ return nullPartitionIndices{lo, hi, hi, hi}
+ }
+ if nullPlacement == NullsAtStart {
+ t := 0
+ for i := lo; i < hi; i++ {
+ if isNullLike(indices[i]) {
+ scratch[lo+t] = indices[i]
+ t++
+ }
+ }
+ likeEnd := lo + t
+ u := t
+ for i := lo; i < hi; i++ {
+ if !isNullLike(indices[i]) {
+ scratch[lo+u] = indices[i]
+ u++
+ }
+ }
+ copy(indices[lo:hi], scratch[lo:hi])
+ return nullPartitionIndices{likeEnd, hi, lo, likeEnd}
+ }
+ t := 0
+ for i := lo; i < hi; i++ {
+ if !isNullLike(indices[i]) {
+ scratch[lo+t] = indices[i]
+ t++
+ }
+ }
+ finEnd := lo + t
+ u := t
+ for i := lo; i < hi; i++ {
+ if isNullLike(indices[i]) {
+ scratch[lo+u] = indices[i]
+ u++
+ }
+ }
+ copy(indices[lo:hi], scratch[lo:hi])
+ return nullPartitionIndices{lo, finEnd, finEnd, hi}
+}
+
+// nullPartitionNoValidityNulls is PartitionNullsOnly when null_count == 0 (vector_sort_internal.h).
+func nullPartitionNoValidityNulls(lo, hi int, nullPlacement NullPlacement) nullPartitionIndices {
+ if nullPlacement == NullsAtStart {
+ return nullPartitionIndices{lo, hi, lo, lo}
+ }
+ return nullPartitionIndices{lo, hi, hi, hi}
+}
Review Comment:
this is identical to some conditions above, can we just call this there instead of duplicating the lines? like lines 45, 95, 108 etc
##########
arrow/compute/internal/kernels/vector_sort.go:
##########
@@ -0,0 +1,476 @@
+// 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.
+
+//go:build go1.18
+
+package kernels
+
+import (
+ "fmt"
+ "slices"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/compute/exec"
+)
+
+// SortOrder specifies the sort order for sorting operations.
+type SortOrder int8
+
+const (
+ Ascending SortOrder = iota
+ Descending
+)
+
+// NullPlacement specifies where null values should be placed in the sort order.
+type NullPlacement int8
+
+const (
+ NullsAtEnd NullPlacement = iota
+ NullsAtStart
+)
+
+// SortOptions defines options for the sort_indices function.
+type SortOptions struct {
+ Order SortOrder `compute:"order"`
+ NullPlacement NullPlacement `compute:"null_placement"`
+}
+
+func (SortOptions) TypeName() string { return "SortOptions" }
+
+type SortState = SortOptions
+
+// SortKey defines a column to sort by with its ordering and null placement options.
+type SortKey struct {
+ ColumnIndex int
+ Order SortOrder
+ NullPlacement NullPlacement
+}
+
+// Chunk-aware sort_indices: logical row IDs 0..n-1, no chunk concatenation. Structure follows
+// Apache Arrow C++ vector_sort.cc / vector_sort_internal.h (see vector_sort_internal.go).
+//
+// Per-column data uses a dense logicalRowMap for O(1) chunk resolution under random compares.
+// Each sortable physical type has a dedicated comparator struct in vector_sort_physical.go (C++
+// ConcreteColumnComparator<T> shape): full monomorphization for the hot compare path; no
+// value-level compare func pointer.
+// compareRowsForKey implements the same ordering as C++ (null placement, NaN, Order).
+//
+// Single key: ChunkedArraySorter — arraySortOneColumnRange per chunk (PartitionNullsOnly /
+// PartitionNullLikes + stable_sort finites), then pairwise merge (ChunkedMergeImpl-style merge
+// using full row order; C++ splits null / non-null merge when the type has null-likes).
+//
+// Multi-key, aligned chunks: TableSorter — per-chunk RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter, then merge.
+//
+// Multi-key, single segment: RadixRecordBatchSorter (<= maxRadixSortKeys) or
+// MultipleKeyRecordBatchSorter (> maxRadixSortKeys).
+
+// maxRadixSortKeys matches Arrow C++ kMaxRadixSortKeys (vector_sort.cc): above this, one global
+// multi-key stable sort is used instead of MSD radix.
+const maxRadixSortKeys = 8
+
+// columnComparator is the Go analogue of compute::internal::ColumnComparator (vector_sort_internal.h):
+// per-column row compare + null / null-like metadata for partitioning.
+type columnComparator interface {
+ // compareRowsForKey returns -1 if i before j, +1 if i after j, 0 if tied on this column
+ // (both null, or both non-null and equal), so the caller may advance to the next sort key.
+ compareRowsForKey(i, j uint64, key SortKey) int
+ // isNullAt returns true if the global row index is null.
+ isNullAt(global uint64) bool
+ // hasNullLikeValues returns true if the column has null-like values.
+ hasNullLikeValues() bool
+ // isNullLikeAt returns true if the global row index is a null-like value.
+ isNullLikeAt(global uint64) bool
+ // columnHasValidityNulls mirrors Array::null_count() != 0; when false, C++ skips PartitionNullsOnly.
+ columnHasValidityNulls() bool
+}
+
+// multiColumnComparator compares two logical rows (global uint64 indices) lexicographically
+// across every sort key. That matches C++ MultipleKeyComparator::CompareInternal(left, right, 0)
+// (vector_sort_internal.h), but it is not a port of the whole MultipleKeyComparator type: C++ keeps
+// ResolvedSortKey per column, uses Location (int64 batch row vs ChunkLocation on tables), builds
+// virtual ColumnComparator instances, and passes start_sort_key_index for radix tails and other
+// partial key ranges — in Go those suffix compares are makeTailComparator(comparators, keys, from).
+type multiColumnComparator struct {
+ columns []columnComparator
+ keys []SortKey
+}
+
+// compare is a three-way ordering for stable sort / merge: negative if idxA before idxB, etc.
+func (m *multiColumnComparator) compare(idxA, idxB uint64) int {
+ for i, key := range m.keys {
+ if cmpVal := m.columns[i].compareRowsForKey(idxA, idxB, key); cmpVal != 0 {
+ return cmpVal
+ }
+ }
+ return 0
+}
+
+func extensionStorageFixedSizeBinaryChunks(chunks []arrow.Array) ([]arrow.Array, error) {
+ out := make([]arrow.Array, len(chunks))
+ for i, ch := range chunks {
+ ext, ok := ch.(array.ExtensionArray)
+ if !ok {
+ return nil, fmt.Errorf("%w: extension column must implement array.ExtensionArray", arrow.ErrInvalid)
+ }
+ st := ext.Storage()
+ if st.DataType().ID() != arrow.FIXED_SIZE_BINARY {
+ return nil, fmt.Errorf("%w: sorting extension columns is only supported when storage is fixed_size_binary (got %s)",
+ arrow.ErrNotImplemented, st.DataType())
+ }
+ out[i] = st
+ }
+ return out, nil
+}
+
+func newFixedSizeBinaryComparator(chunks []arrow.Array, numRows int, vn bool) (columnComparator, error) {
+ f0, ok := chunks[0].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ w := f0.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ for i := 1; i < len(chunks); i++ {
+ fi, ok := chunks[i].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ wi := fi.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ if wi != w {
+ return nil, fmt.Errorf("%w: fixed_size_binary chunks must have the same byte width (%d vs %d)",
+ arrow.ErrInvalid, w, wi)
+ }
+ }
+ return newPhysicalSortFixedSizeBinaryColumn(chunks, numRows, vn), nil
+}
+
+// createChunkedComparator builds a column comparator for these chunks (one Arrow type for all chunks).
+func createChunkedComparator(chunks []arrow.Array, numRows int) (columnComparator, error) {
+ if len(chunks) == 0 {
+ return nil, fmt.Errorf("%w: cannot create comparator for empty chunk list", arrow.ErrInvalid)
+ }
+ if totalChunkRows(chunks) != numRows {
+ return nil, fmt.Errorf("%w: chunk row count does not match column length", arrow.ErrInvalid)
+ }
+
+ validityNulls := chunksHaveNulls(chunks)
+ typeID := chunks[0].DataType().ID()
+ switch typeID {
+ case arrow.INT8:
+ return newPhysicalSortInt8Column(chunks, numRows, validityNulls), nil
+ case arrow.INT16:
+ return newPhysicalSortInt16Column(chunks, numRows, validityNulls), nil
+ case arrow.INT32:
+ return newPhysicalSortInt32Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE32:
+ return newPhysicalSortDate32Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME32:
+ return newPhysicalSortTime32Column(chunks, numRows, validityNulls), nil
+ case arrow.INT64:
+ return newPhysicalSortInt64Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE64:
+ return newPhysicalSortDate64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME64:
+ return newPhysicalSortTime64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIMESTAMP:
+ return newPhysicalSortTimestampColumn(chunks, numRows, validityNulls), nil
+ case arrow.DURATION:
+ return newPhysicalSortDurationColumn(chunks, numRows, validityNulls), nil
+ case arrow.UINT8:
+ return newPhysicalSortUint8Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT16:
+ return newPhysicalSortUint16Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT32:
+ return newPhysicalSortUint32Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT64:
+ return newPhysicalSortUint64Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT16:
+ return newPhysicalSortFloat16Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT32:
+ return newPhysicalSortFloat32Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT64:
+ return newPhysicalSortFloat64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL32:
+ return newPhysicalSortDecimal32Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL64:
+ return newPhysicalSortDecimal64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL128:
+ return newPhysicalSortDecimal128Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL256:
+ return newPhysicalSortDecimal256Column(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTHS:
+ return newPhysicalSortMonthIntervalColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_DAY_TIME:
+ return newPhysicalSortDayTimeColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTH_DAY_NANO:
+ return newPhysicalSortMonthDayNanoColumn(chunks, numRows, validityNulls), nil
+ case arrow.BOOL:
+ return newPhysicalSortBoolColumn(chunks, numRows, validityNulls), nil
+ case arrow.STRING:
+ return newPhysicalSortStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_STRING:
+ return newPhysicalSortLargeStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.BINARY:
+ return newPhysicalSortBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_BINARY:
+ return newPhysicalSortLargeBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.FIXED_SIZE_BINARY:
+ return newFixedSizeBinaryComparator(chunks, numRows, validityNulls)
+ case arrow.EXTENSION:
+ storageChunks, err := extensionStorageFixedSizeBinaryChunks(chunks)
+ if err != nil {
+ return nil, err
+ }
+ return newFixedSizeBinaryComparator(storageChunks, numRows, validityNulls)
+ default:
+ return nil, fmt.Errorf("%w: sorting not supported for type %s", arrow.ErrNotImplemented, typeID)
+ }
+}
+
+// chunkIndexSpan represents a contiguous range of indices in the global order.
+type chunkIndexSpan struct {
+ lo, hi int
+}
+
+// mergeAdjacentStable merges sorted adjacent ranges [a0,a1) and [b0,b1) (a1 == b0) into indices[lo:hi]
+// using a strict weak order: i is ordered before j iff less(i,j). Tie-breaking prefers the left range
+// (stable merge, same as C++ std::merge with !comp(right,left)).
+func mergeAdjacentStable(indices, tmp []uint64, a0, a1, b0, b1 int, less func(a, b uint64) bool) {
+ i, j, k := a0, b0, a0
+ for i < a1 && j < b1 {
+ if !less(indices[j], indices[i]) {
+ tmp[k] = indices[i]
+ i++
+ } else {
+ tmp[k] = indices[j]
+ j++
+ }
+ k++
+ }
+ for i < a1 {
+ tmp[k] = indices[i]
+ k++
+ i++
+ }
+ for j < b1 {
+ tmp[k] = indices[j]
+ k++
+ j++
+ }
+ copy(indices[a0:b1], tmp[a0:b1])
+}
+
+// pairwiseMergeSortedSpans merges already-sorted adjacent index spans (chunk batch rows in global
+// order), matching Arrow C++ ChunkedMergeImpl / TableSorter batch merge (vector_sort.cc).
+// spanScratch must have capacity >= len(spans); it ping-pongs with spans' backing during merging.
+func pairwiseMergeSortedSpans(indices, tmp []uint64, spans []chunkIndexSpan, less func(a, b uint64) bool, spanScratch []chunkIndexSpan) {
+ if len(spans) <= 1 {
+ return
+ }
+ if cap(spanScratch) < len(spans) {
+ panic("kernels: spanScratch cap < len(spans)")
+ }
+ cur := spans
+ other := spanScratch[:0]
+ for len(cur) > 1 {
+ other = other[:0]
+ for i := 0; i < len(cur); i += 2 {
+ if i+1 < len(cur) {
+ s0, s1 := cur[i], cur[i+1]
+ mergeAdjacentStable(indices, tmp, s0.lo, s0.hi, s1.lo, s1.hi, less)
+ other = append(other, chunkIndexSpan{s0.lo, s1.hi})
+ } else {
+ other = append(other, cur[i])
+ }
+ }
+ cur, other = other, cur
+ }
+}
+
+// alignedChunkBoundaries reports cumulative row offsets for chunk boundaries when every sort column
+// has the same chunk count and matching chunk lengths (typical for Arrow tables).
+func alignedChunkBoundaries(columns []*arrow.Chunked) ([]int, bool) {
+ if len(columns) == 0 {
+ return nil, false
+ }
+ ch0 := columns[0].Chunks()
+ n := len(ch0)
+ if n == 0 {
+ return nil, false
+ }
+ offs := make([]int, n+1)
+ for i := 0; i < n; i++ {
+ L := ch0[i].Len()
+ for j := 1; j < len(columns); j++ {
+ cj := columns[j].Chunks()
+ if len(cj) != n || cj[i].Len() != L {
+ return nil, false
+ }
+ }
+ offs[i+1] = offs[i] + L
+ }
+ if offs[n] != columns[0].Len() {
+ return nil, false
+ }
+ return offs, true
+}
+
+// sortIndicesSingleColumnChunked implements Arrow C++ ChunkedArraySorter for one logical column:
+// per-chunk array sort (partition + sort finites), then pairwise merge (ChunkedMergeImpl).
+func sortIndicesSingleColumnChunked(indices []uint64, chunks []arrow.Array, comp columnComparator, key SortKey, tmp []uint64, spanScratch []chunkIndexSpan) {
+ lo := 0
+ for _, ch := range chunks {
+ hi := lo + ch.Len()
+ arraySortOneColumnRange(indices, tmp, comp, key, lo, hi)
+ lo = hi
+ }
+
+ nChunks := len(chunks)
+ if nChunks <= 1 {
+ return
+ }
+
+ less := func(a, b uint64) bool { return comp.compareRowsForKey(a, b, key) < 0 }
+
+ spans := make([]chunkIndexSpan, nChunks)
+ lo = 0
+ for i, ch := range chunks {
+ hi := lo + ch.Len()
+ spans[i] = chunkIndexSpan{lo, hi}
+ lo = hi
+ }
+ pairwiseMergeSortedSpans(indices, tmp, spans, less, spanScratch)
+}
+
+// sortIndicesMultiColumnAlignedChunks sorts each aligned chunk (C++ RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter), then merges like Arrow C++ TableSorter.
+func sortIndicesMultiColumnAlignedChunks(indices []uint64, offs []int, comparators []columnComparator, keys []SortKey, multiComp *multiColumnComparator, tmp []uint64, spanScratch []chunkIndexSpan) {
+ nChunks := len(offs) - 1
+ useRadix := len(keys) <= maxRadixSortKeys
+ for c := 0; c < nChunks; c++ {
+ lo, hi := offs[c], offs[c+1]
+ if useRadix {
+ radixRecordBatchSortRange(indices, tmp, comparators, keys, 0, lo, hi)
+ } else {
+ multipleKeyRecordBatchSortRange(indices, tmp, comparators, keys, lo, hi, makeTailComparator(comparators, keys, 1))
+ }
+ }
+ if nChunks <= 1 {
+ return
+ }
+ less := func(a, b uint64) bool { return multiComp.compare(a, b) < 0 }
+ spans := make([]chunkIndexSpan, nChunks)
+ for c := 0; c < nChunks; c++ {
+ spans[c] = chunkIndexSpan{offs[c], offs[c+1]}
+ }
+ pairwiseMergeSortedSpans(indices, tmp, spans, less, spanScratch)
+}
+
+// SortIndices returns a stable permutation of 0..n-1 that would lexicographically sort the given
+// columns. Each *arrow.Chunked is used via its .Chunks() only—no concatenate. columns[i] pairs with
+// keys[i] for order and null placement on that column.
+func SortIndices(ctx *exec.KernelCtx, columns []*arrow.Chunked, keys []SortKey) (*exec.ExecResult, error) {
+ if len(columns) == 0 || len(keys) == 0 {
+ return nil, fmt.Errorf("%w: must have at least one column and one sort key", arrow.ErrInvalid)
+ }
+
+ if len(columns) != len(keys) {
+ return nil, fmt.Errorf("%w: number of columns (%d) must match number of sort keys (%d)",
+ arrow.ErrInvalid, len(columns), len(keys))
+ }
+
+ length := int64(columns[0].Len())
+ for _, col := range columns {
+ if int64(col.Len()) != length {
+ return nil, fmt.Errorf("%w: all columns must have the same length", arrow.ErrInvalid)
+ }
+ }
+
+ comparators := make([]columnComparator, len(columns))
+ nRows := int(length)
+ for i, col := range columns {
+ comp, err := createChunkedComparator(col.Chunks(), nRows)
+ if err != nil {
+ return nil, err
+ }
+ comparators[i] = comp
+ }
+
+ multiComp := &multiColumnComparator{
+ columns: comparators,
+ keys: keys,
+ }
+
+ out := &exec.ExecResult{}
+ out.Len = length
+ out.Type = arrow.PrimitiveTypes.Uint64
+ out.Nulls = 0
+
+ buf := ctx.Allocate(int(length) * arrow.Uint64SizeBytes)
+ indices := arrow.Uint64Traits.CastFromBytes(buf.Buf())[:length]
+
+ for i := range indices {
+ indices[i] = uint64(i)
+ }
+
+ if len(keys) == 1 {
+ chunks := columns[0].Chunks()
+ if len(chunks) > 1 {
+ tmpBuf := ctx.Allocate(nRows * arrow.Uint64SizeBytes)
+ tmp := arrow.Uint64Traits.CastFromBytes(tmpBuf.Buf())[:nRows]
+ spanScratch := make([]chunkIndexSpan, len(chunks))
+ sortIndicesSingleColumnChunked(indices, chunks, comparators[0], keys[0], tmp, spanScratch)
+ } else {
+ k0 := keys[0]
+ c0 := comparators[0]
Review Comment:
same comment as above
##########
arrow/compute/internal/kernels/vector_sort.go:
##########
@@ -0,0 +1,476 @@
+// 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.
+
+//go:build go1.18
+
+package kernels
+
+import (
+ "fmt"
+ "slices"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+ "github.com/apache/arrow-go/v18/arrow/compute/exec"
+)
+
+// SortOrder specifies the sort order for sorting operations.
+type SortOrder int8
+
+const (
+ Ascending SortOrder = iota
+ Descending
+)
+
+// NullPlacement specifies where null values should be placed in the sort order.
+type NullPlacement int8
+
+const (
+ NullsAtEnd NullPlacement = iota
+ NullsAtStart
+)
+
+// SortOptions defines options for the sort_indices function.
+type SortOptions struct {
+ Order SortOrder `compute:"order"`
+ NullPlacement NullPlacement `compute:"null_placement"`
+}
+
+func (SortOptions) TypeName() string { return "SortOptions" }
+
+type SortState = SortOptions
+
+// SortKey defines a column to sort by with its ordering and null placement options.
+type SortKey struct {
+ ColumnIndex int
+ Order SortOrder
+ NullPlacement NullPlacement
+}
+
+// Chunk-aware sort_indices: logical row IDs 0..n-1, no chunk concatenation. Structure follows
+// Apache Arrow C++ vector_sort.cc / vector_sort_internal.h (see vector_sort_internal.go).
+//
+// Per-column data uses a dense logicalRowMap for O(1) chunk resolution under random compares.
+// Each sortable physical type has a dedicated comparator struct in vector_sort_physical.go (C++
+// ConcreteColumnComparator<T> shape): full monomorphization for the hot compare path; no
+// value-level compare func pointer.
+// compareRowsForKey implements the same ordering as C++ (null placement, NaN, Order).
+//
+// Single key: ChunkedArraySorter — arraySortOneColumnRange per chunk (PartitionNullsOnly /
+// PartitionNullLikes + stable_sort finites), then pairwise merge (ChunkedMergeImpl-style merge
+// using full row order; C++ splits null / non-null merge when the type has null-likes).
+//
+// Multi-key, aligned chunks: TableSorter — per-chunk RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter, then merge.
+//
+// Multi-key, single segment: RadixRecordBatchSorter (<= maxRadixSortKeys) or
+// MultipleKeyRecordBatchSorter (> maxRadixSortKeys).
+
+// maxRadixSortKeys matches Arrow C++ kMaxRadixSortKeys (vector_sort.cc): above this, one global
+// multi-key stable sort is used instead of MSD radix.
+const maxRadixSortKeys = 8
+
+// columnComparator is the Go analogue of compute::internal::ColumnComparator (vector_sort_internal.h):
+// per-column row compare + null / null-like metadata for partitioning.
+type columnComparator interface {
+ // compareRowsForKey returns -1 if i before j, +1 if i after j, 0 if tied on this column
+ // (both null, or both non-null and equal), so the caller may advance to the next sort key.
+ compareRowsForKey(i, j uint64, key SortKey) int
+ // isNullAt returns true if the global row index is null.
+ isNullAt(global uint64) bool
+ // hasNullLikeValues returns true if the column has null-like values.
+ hasNullLikeValues() bool
+ // isNullLikeAt returns true if the global row index is a null-like value.
+ isNullLikeAt(global uint64) bool
+ // columnHasValidityNulls mirrors Array::null_count() != 0; when false, C++ skips PartitionNullsOnly.
+ columnHasValidityNulls() bool
+}
+
+// multiColumnComparator compares two logical rows (global uint64 indices) lexicographically
+// across every sort key. That matches C++ MultipleKeyComparator::CompareInternal(left, right, 0)
+// (vector_sort_internal.h), but it is not a port of the whole MultipleKeyComparator type: C++ keeps
+// ResolvedSortKey per column, uses Location (int64 batch row vs ChunkLocation on tables), builds
+// virtual ColumnComparator instances, and passes start_sort_key_index for radix tails and other
+// partial key ranges — in Go those suffix compares are makeTailComparator(comparators, keys, from).
+type multiColumnComparator struct {
+ columns []columnComparator
+ keys []SortKey
+}
+
+// compare is a three-way ordering for stable sort / merge: negative if idxA before idxB, etc.
+func (m *multiColumnComparator) compare(idxA, idxB uint64) int {
+ for i, key := range m.keys {
+ if cmpVal := m.columns[i].compareRowsForKey(idxA, idxB, key); cmpVal != 0 {
+ return cmpVal
+ }
+ }
+ return 0
+}
+
+func extensionStorageFixedSizeBinaryChunks(chunks []arrow.Array) ([]arrow.Array, error) {
+ out := make([]arrow.Array, len(chunks))
+ for i, ch := range chunks {
+ ext, ok := ch.(array.ExtensionArray)
+ if !ok {
+ return nil, fmt.Errorf("%w: extension column must implement array.ExtensionArray", arrow.ErrInvalid)
+ }
+ st := ext.Storage()
+ if st.DataType().ID() != arrow.FIXED_SIZE_BINARY {
+ return nil, fmt.Errorf("%w: sorting extension columns is only supported when storage is fixed_size_binary (got %s)",
+ arrow.ErrNotImplemented, st.DataType())
+ }
+ out[i] = st
+ }
+ return out, nil
+}
+
+func newFixedSizeBinaryComparator(chunks []arrow.Array, numRows int, vn bool) (columnComparator, error) {
+ f0, ok := chunks[0].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ w := f0.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ for i := 1; i < len(chunks); i++ {
+ fi, ok := chunks[i].(*array.FixedSizeBinary)
+ if !ok {
+ return nil, fmt.Errorf("%w: expected *array.FixedSizeBinary chunk", arrow.ErrInvalid)
+ }
+ wi := fi.DataType().(*arrow.FixedSizeBinaryType).ByteWidth
+ if wi != w {
+ return nil, fmt.Errorf("%w: fixed_size_binary chunks must have the same byte width (%d vs %d)",
+ arrow.ErrInvalid, w, wi)
+ }
+ }
+ return newPhysicalSortFixedSizeBinaryColumn(chunks, numRows, vn), nil
+}
+
+// createChunkedComparator builds a column comparator for these chunks (one Arrow type for all chunks).
+func createChunkedComparator(chunks []arrow.Array, numRows int) (columnComparator, error) {
+ if len(chunks) == 0 {
+ return nil, fmt.Errorf("%w: cannot create comparator for empty chunk list", arrow.ErrInvalid)
+ }
+ if totalChunkRows(chunks) != numRows {
+ return nil, fmt.Errorf("%w: chunk row count does not match column length", arrow.ErrInvalid)
+ }
+
+ validityNulls := chunksHaveNulls(chunks)
+ typeID := chunks[0].DataType().ID()
+ switch typeID {
+ case arrow.INT8:
+ return newPhysicalSortInt8Column(chunks, numRows, validityNulls), nil
+ case arrow.INT16:
+ return newPhysicalSortInt16Column(chunks, numRows, validityNulls), nil
+ case arrow.INT32:
+ return newPhysicalSortInt32Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE32:
+ return newPhysicalSortDate32Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME32:
+ return newPhysicalSortTime32Column(chunks, numRows, validityNulls), nil
+ case arrow.INT64:
+ return newPhysicalSortInt64Column(chunks, numRows, validityNulls), nil
+ case arrow.DATE64:
+ return newPhysicalSortDate64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIME64:
+ return newPhysicalSortTime64Column(chunks, numRows, validityNulls), nil
+ case arrow.TIMESTAMP:
+ return newPhysicalSortTimestampColumn(chunks, numRows, validityNulls), nil
+ case arrow.DURATION:
+ return newPhysicalSortDurationColumn(chunks, numRows, validityNulls), nil
+ case arrow.UINT8:
+ return newPhysicalSortUint8Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT16:
+ return newPhysicalSortUint16Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT32:
+ return newPhysicalSortUint32Column(chunks, numRows, validityNulls), nil
+ case arrow.UINT64:
+ return newPhysicalSortUint64Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT16:
+ return newPhysicalSortFloat16Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT32:
+ return newPhysicalSortFloat32Column(chunks, numRows, validityNulls), nil
+ case arrow.FLOAT64:
+ return newPhysicalSortFloat64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL32:
+ return newPhysicalSortDecimal32Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL64:
+ return newPhysicalSortDecimal64Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL128:
+ return newPhysicalSortDecimal128Column(chunks, numRows, validityNulls), nil
+ case arrow.DECIMAL256:
+ return newPhysicalSortDecimal256Column(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTHS:
+ return newPhysicalSortMonthIntervalColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_DAY_TIME:
+ return newPhysicalSortDayTimeColumn(chunks, numRows, validityNulls), nil
+ case arrow.INTERVAL_MONTH_DAY_NANO:
+ return newPhysicalSortMonthDayNanoColumn(chunks, numRows, validityNulls), nil
+ case arrow.BOOL:
+ return newPhysicalSortBoolColumn(chunks, numRows, validityNulls), nil
+ case arrow.STRING:
+ return newPhysicalSortStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_STRING:
+ return newPhysicalSortLargeStringColumn(chunks, numRows, validityNulls), nil
+ case arrow.BINARY:
+ return newPhysicalSortBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.LARGE_BINARY:
+ return newPhysicalSortLargeBinaryColumn(chunks, numRows, validityNulls), nil
+ case arrow.FIXED_SIZE_BINARY:
+ return newFixedSizeBinaryComparator(chunks, numRows, validityNulls)
+ case arrow.EXTENSION:
+ storageChunks, err := extensionStorageFixedSizeBinaryChunks(chunks)
+ if err != nil {
+ return nil, err
+ }
+ return newFixedSizeBinaryComparator(storageChunks, numRows, validityNulls)
+ default:
+ return nil, fmt.Errorf("%w: sorting not supported for type %s", arrow.ErrNotImplemented, typeID)
+ }
+}
+
+// chunkIndexSpan represents a contiguous range of indices in the global order.
+type chunkIndexSpan struct {
+ lo, hi int
+}
+
+// mergeAdjacentStable merges sorted adjacent ranges [a0,a1) and [b0,b1) (a1 == b0) into indices[lo:hi]
+// using a strict weak order: i is ordered before j iff less(i,j). Tie-breaking prefers the left range
+// (stable merge, same as C++ std::merge with !comp(right,left)).
+func mergeAdjacentStable(indices, tmp []uint64, a0, a1, b0, b1 int, less func(a, b uint64) bool) {
+ i, j, k := a0, b0, a0
+ for i < a1 && j < b1 {
+ if !less(indices[j], indices[i]) {
+ tmp[k] = indices[i]
+ i++
+ } else {
+ tmp[k] = indices[j]
+ j++
+ }
+ k++
+ }
+ for i < a1 {
+ tmp[k] = indices[i]
+ k++
+ i++
+ }
+ for j < b1 {
+ tmp[k] = indices[j]
+ k++
+ j++
+ }
+ copy(indices[a0:b1], tmp[a0:b1])
+}
+
+// pairwiseMergeSortedSpans merges already-sorted adjacent index spans (chunk batch rows in global
+// order), matching Arrow C++ ChunkedMergeImpl / TableSorter batch merge (vector_sort.cc).
+// spanScratch must have capacity >= len(spans); it ping-pongs with spans' backing during merging.
+func pairwiseMergeSortedSpans(indices, tmp []uint64, spans []chunkIndexSpan, less func(a, b uint64) bool, spanScratch []chunkIndexSpan) {
+ if len(spans) <= 1 {
+ return
+ }
+ if cap(spanScratch) < len(spans) {
+ panic("kernels: spanScratch cap < len(spans)")
+ }
+ cur := spans
+ other := spanScratch[:0]
+ for len(cur) > 1 {
+ other = other[:0]
+ for i := 0; i < len(cur); i += 2 {
+ if i+1 < len(cur) {
+ s0, s1 := cur[i], cur[i+1]
+ mergeAdjacentStable(indices, tmp, s0.lo, s0.hi, s1.lo, s1.hi, less)
+ other = append(other, chunkIndexSpan{s0.lo, s1.hi})
+ } else {
+ other = append(other, cur[i])
+ }
+ }
+ cur, other = other, cur
+ }
+}
+
+// alignedChunkBoundaries reports cumulative row offsets for chunk boundaries when every sort column
+// has the same chunk count and matching chunk lengths (typical for Arrow tables).
+func alignedChunkBoundaries(columns []*arrow.Chunked) ([]int, bool) {
+ if len(columns) == 0 {
+ return nil, false
+ }
+ ch0 := columns[0].Chunks()
+ n := len(ch0)
+ if n == 0 {
+ return nil, false
+ }
+ offs := make([]int, n+1)
+ for i := 0; i < n; i++ {
+ L := ch0[i].Len()
+ for j := 1; j < len(columns); j++ {
+ cj := columns[j].Chunks()
+ if len(cj) != n || cj[i].Len() != L {
+ return nil, false
+ }
+ }
+ offs[i+1] = offs[i] + L
+ }
+ if offs[n] != columns[0].Len() {
+ return nil, false
+ }
+ return offs, true
+}
+
+// sortIndicesSingleColumnChunked implements Arrow C++ ChunkedArraySorter for one logical column:
+// per-chunk array sort (partition + sort finites), then pairwise merge (ChunkedMergeImpl).
+func sortIndicesSingleColumnChunked(indices []uint64, chunks []arrow.Array, comp columnComparator, key SortKey, tmp []uint64, spanScratch []chunkIndexSpan) {
+ lo := 0
+ for _, ch := range chunks {
+ hi := lo + ch.Len()
+ arraySortOneColumnRange(indices, tmp, comp, key, lo, hi)
+ lo = hi
+ }
+
+ nChunks := len(chunks)
+ if nChunks <= 1 {
+ return
+ }
+
+ less := func(a, b uint64) bool { return comp.compareRowsForKey(a, b, key) < 0 }
+
+ spans := make([]chunkIndexSpan, nChunks)
+ lo = 0
+ for i, ch := range chunks {
+ hi := lo + ch.Len()
+ spans[i] = chunkIndexSpan{lo, hi}
+ lo = hi
+ }
+ pairwiseMergeSortedSpans(indices, tmp, spans, less, spanScratch)
+}
+
+// sortIndicesMultiColumnAlignedChunks sorts each aligned chunk (C++ RadixRecordBatchSorter or
+// MultipleKeyRecordBatchSorter), then merges like Arrow C++ TableSorter.
+func sortIndicesMultiColumnAlignedChunks(indices []uint64, offs []int, comparators []columnComparator, keys []SortKey, multiComp *multiColumnComparator, tmp []uint64, spanScratch []chunkIndexSpan) {
+ nChunks := len(offs) - 1
+ useRadix := len(keys) <= maxRadixSortKeys
+ for c := 0; c < nChunks; c++ {
+ lo, hi := offs[c], offs[c+1]
+ if useRadix {
+ radixRecordBatchSortRange(indices, tmp, comparators, keys, 0, lo, hi)
+ } else {
+ multipleKeyRecordBatchSortRange(indices, tmp, comparators, keys, lo, hi, makeTailComparator(comparators, keys, 1))
+ }
+ }
+ if nChunks <= 1 {
+ return
+ }
+ less := func(a, b uint64) bool { return multiComp.compare(a, b) < 0 }
+ spans := make([]chunkIndexSpan, nChunks)
+ for c := 0; c < nChunks; c++ {
+ spans[c] = chunkIndexSpan{offs[c], offs[c+1]}
+ }
+ pairwiseMergeSortedSpans(indices, tmp, spans, less, spanScratch)
+}
+
+// SortIndices returns a stable permutation of 0..n-1 that would lexicographically sort the given
+// columns. Each *arrow.Chunked is used via its .Chunks() only—no concatenate. columns[i] pairs with
+// keys[i] for order and null placement on that column.
+func SortIndices(ctx *exec.KernelCtx, columns []*arrow.Chunked, keys []SortKey) (*exec.ExecResult, error) {
+ if len(columns) == 0 || len(keys) == 0 {
+ return nil, fmt.Errorf("%w: must have at least one column and one sort key", arrow.ErrInvalid)
+ }
+
+ if len(columns) != len(keys) {
+ return nil, fmt.Errorf("%w: number of columns (%d) must match number of sort keys (%d)",
+ arrow.ErrInvalid, len(columns), len(keys))
+ }
+
+ length := int64(columns[0].Len())
+ for _, col := range columns {
+ if int64(col.Len()) != length {
+ return nil, fmt.Errorf("%w: all columns must have the same length", arrow.ErrInvalid)
+ }
+ }
+
+ comparators := make([]columnComparator, len(columns))
+ nRows := int(length)
+ for i, col := range columns {
+ comp, err := createChunkedComparator(col.Chunks(), nRows)
+ if err != nil {
+ return nil, err
+ }
+ comparators[i] = comp
+ }
+
+ multiComp := &multiColumnComparator{
+ columns: comparators,
+ keys: keys,
+ }
+
+ out := &exec.ExecResult{}
+ out.Len = length
+ out.Type = arrow.PrimitiveTypes.Uint64
+ out.Nulls = 0
+
+ buf := ctx.Allocate(int(length) * arrow.Uint64SizeBytes)
+ indices := arrow.Uint64Traits.CastFromBytes(buf.Buf())[:length]
+
+ for i := range indices {
+ indices[i] = uint64(i)
+ }
+
+ if len(keys) == 1 {
+ chunks := columns[0].Chunks()
+ if len(chunks) > 1 {
+ tmpBuf := ctx.Allocate(nRows * arrow.Uint64SizeBytes)
+ tmp := arrow.Uint64Traits.CastFromBytes(tmpBuf.Buf())[:nRows]
+ spanScratch := make([]chunkIndexSpan, len(chunks))
+ sortIndicesSingleColumnChunked(indices, chunks, comparators[0], keys[0], tmp, spanScratch)
Review Comment:
same as above, shouldn't it be `comparators[keys[0].ColumnIndex]`?
##########
arrow/compute/internal/kernels/vector_sort_internal.go:
##########
@@ -0,0 +1,280 @@
+// 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.
+
+//go:build go1.18
+
+package kernels
+
+import (
+ "slices"
+)
+
+// Ported from Apache Arrow C++ vector_sort_internal.h / vector_sort.cc:
+// GenericNullPartitionResult, PartitionNullsOnly, PartitionNullLikes, VisitConstantRanges,
+// ConcreteRecordBatchColumnSorter::SortRange (radix / column-wise multi-key path).
+
+// nullPartitionIndices holds inclusive-exclusive offsets into the indices buffer (like uint64_t*
+// ranges in C++ GenericNullPartitionResult).
+type nullPartitionIndices struct {
+ nonNullsLo, nonNullsHi int
+ nullsLo, nullsHi int
+}
+
+// partitionNullsOnly mirrors PartitionNullsOnly<StablePartitioner> in vector_sort_internal.h.
+func partitionNullsOnly(indices, scratch []uint64, lo, hi int, nullPlacement NullPlacement, isNull func(uint64) bool) nullPartitionIndices {
+ if lo >= hi {
+ return nullPartitionIndices{lo, lo, lo, lo}
+ }
+ hasNull := false
+ for i := lo; i < hi; i++ {
+ if isNull(indices[i]) {
+ hasNull = true
+ break
+ }
+ }
+ if !hasNull {
+ if nullPlacement == NullsAtStart {
+ return nullPartitionIndices{lo, hi, lo, lo}
+ }
+ return nullPartitionIndices{lo, hi, hi, hi}
+ }
+ if nullPlacement == NullsAtStart {
+ t := 0
+ for i := lo; i < hi; i++ {
+ if isNull(indices[i]) {
+ scratch[lo+t] = indices[i]
+ t++
+ }
+ }
+ nullEnd := lo + t
+ u := t
+ for i := lo; i < hi; i++ {
+ if !isNull(indices[i]) {
+ scratch[lo+u] = indices[i]
+ u++
+ }
+ }
+ copy(indices[lo:hi], scratch[lo:hi])
+ return nullPartitionIndices{nullEnd, hi, lo, nullEnd}
+ }
+ t := 0
+ for i := lo; i < hi; i++ {
+ if !isNull(indices[i]) {
+ scratch[lo+t] = indices[i]
+ t++
+ }
+ }
+ nnEnd := lo + t
+ u := t
+ for i := lo; i < hi; i++ {
+ if isNull(indices[i]) {
+ scratch[lo+u] = indices[i]
+ u++
+ }
+ }
+ copy(indices[lo:hi], scratch[lo:hi])
+ return nullPartitionIndices{lo, nnEnd, nnEnd, hi}
+}
+
+// partitionNullLikes mirrors PartitionNullLikes in vector_sort_internal.h (NaN for floats).
+func partitionNullLikes(indices, scratch []uint64, lo, hi int, nullPlacement NullPlacement, hasNullLike bool, isNullLike func(uint64) bool) nullPartitionIndices {
+ if !hasNullLike || lo >= hi {
+ if nullPlacement == NullsAtStart {
+ return nullPartitionIndices{lo, hi, lo, lo}
+ }
+ return nullPartitionIndices{lo, hi, hi, hi}
+ }
+ hasLike := false
+ for i := lo; i < hi; i++ {
+ if isNullLike(indices[i]) {
+ hasLike = true
+ break
+ }
+ }
+ if !hasLike {
+ if nullPlacement == NullsAtStart {
+ return nullPartitionIndices{lo, hi, lo, lo}
+ }
+ return nullPartitionIndices{lo, hi, hi, hi}
+ }
+ if nullPlacement == NullsAtStart {
+ t := 0
+ for i := lo; i < hi; i++ {
+ if isNullLike(indices[i]) {
+ scratch[lo+t] = indices[i]
+ t++
+ }
+ }
+ likeEnd := lo + t
+ u := t
+ for i := lo; i < hi; i++ {
+ if !isNullLike(indices[i]) {
+ scratch[lo+u] = indices[i]
+ u++
+ }
+ }
+ copy(indices[lo:hi], scratch[lo:hi])
+ return nullPartitionIndices{likeEnd, hi, lo, likeEnd}
+ }
+ t := 0
+ for i := lo; i < hi; i++ {
+ if !isNullLike(indices[i]) {
+ scratch[lo+t] = indices[i]
+ t++
+ }
+ }
+ finEnd := lo + t
+ u := t
+ for i := lo; i < hi; i++ {
+ if isNullLike(indices[i]) {
+ scratch[lo+u] = indices[i]
+ u++
+ }
+ }
+ copy(indices[lo:hi], scratch[lo:hi])
+ return nullPartitionIndices{lo, finEnd, finEnd, hi}
+}
+
+// nullPartitionNoValidityNulls is PartitionNullsOnly when null_count == 0 (vector_sort_internal.h).
+func nullPartitionNoValidityNulls(lo, hi int, nullPlacement NullPlacement) nullPartitionIndices {
+ if nullPlacement == NullsAtStart {
+ return nullPartitionIndices{lo, hi, lo, lo}
+ }
+ return nullPartitionIndices{lo, hi, hi, hi}
+}
+
+// visitConstantRanges mirrors VisitConstantRanges in vector_sort.cc.
+func visitConstantRanges(indices []uint64, offsetLo, offsetHi int, key SortKey, comp columnComparator, visit func(rs, re int)) {
+ if offsetHi-offsetLo <= 1 {
+ return
+ }
+ rs := offsetLo
+ for t := offsetLo + 1; t <= offsetHi; t++ {
+ if t < offsetHi && comp.compareRowsForKey(indices[t-1], indices[t], key) == 0 {
+ continue
+ }
+ if t-rs > 0 {
+ visit(rs, t)
+ }
+ rs = t
+ }
+}
+
+// radixRecordBatchSortRange mirrors ConcreteRecordBatchColumnSorter::SortRange in vector_sort.cc.
+func radixRecordBatchSortRange(indices []uint64, scratch []uint64, comparators []columnComparator, keys []SortKey, keyIdx, lo, hi int) {
+ if hi-lo <= 1 || keyIdx >= len(keys) {
+ return
+ }
+ key := keys[keyIdx]
+ comp := comparators[keyIdx]
+
+ var p nullPartitionIndices
+ if comp.columnHasValidityNulls() {
+ p = partitionNullsOnly(indices, scratch, lo, hi, key.NullPlacement, comp.isNullAt)
+ } else {
+ p = nullPartitionNoValidityNulls(lo, hi, key.NullPlacement)
+ }
+ q := partitionNullLikes(indices, scratch, p.nonNullsLo, p.nonNullsHi, key.NullPlacement, comp.hasNullLikeValues(), comp.isNullLikeAt)
+
+ nanLo, nanHi := q.nullsLo, q.nullsHi
+ finiteLo, finiteHi := q.nonNullsLo, q.nonNullsHi
+ nullLo, nullHi := p.nullsLo, p.nullsHi
+
+ slices.SortStableFunc(indices[finiteLo:finiteHi], func(a, b uint64) int {
+ return comp.compareRowsForKey(a, b, key)
+ })
+
+ if keyIdx == len(keys)-1 {
+ return
+ }
+ next := keyIdx + 1
+
+ // Same order as C++: null-likes, true nulls, then tie ranges among finite values.
+ radixRecordBatchSortRange(indices, scratch, comparators, keys, next, nanLo, nanHi)
+ radixRecordBatchSortRange(indices, scratch, comparators, keys, next, nullLo, nullHi)
+ visitConstantRanges(indices, finiteLo, finiteHi, key, comp, func(rs, re int) {
+ radixRecordBatchSortRange(indices, scratch, comparators, keys, next, rs, re)
+ })
+}
+
+// multipleKeyRecordBatchSortRange mirrors MultipleKeyRecordBatchSorter::SortInternal in vector_sort.cc:
+// partition nulls / null-likes on the first key, stable_sort non-null finites with tail comparator.
+func multipleKeyRecordBatchSortRange(indices []uint64, scratch []uint64, comparators []columnComparator, keys []SortKey, lo, hi int, tail func(a, b uint64) int) {
+ if hi-lo <= 1 {
+ return
+ }
+ key := keys[0]
+ comp := comparators[0]
Review Comment:
same comment as before, shouldn't we be using `key.ColumnIndex`?
##########
arrow/compute/internal/kernels/vector_sort_physical.go:
##########
@@ -0,0 +1,873 @@
+// 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.
+
+//go:build go1.18
+
+package kernels
+
+import (
+ "math"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/array"
+)
+
+// physicalColumnBase holds chunked data and row resolution shared by monomorphic sort columns.
+// Each Arrow physical type has its own comparator struct embedding this (no compare func pointer).
+type physicalColumnBase struct {
+ chunks []arrow.Array
+ rowMap logicalRowMap
+ validityNulls bool
+}
+
+func newPhysicalColumnBase(chunks []arrow.Array, numRows int, validityNulls bool) physicalColumnBase {
+ var rowMap logicalRowMap
+ if len(chunks) > 1 {
+ rowMap = newLogicalRowMap(chunks, numRows)
+ }
+ return physicalColumnBase{chunks: chunks, rowMap: rowMap, validityNulls: validityNulls}
+}
+
+// Pointer receivers: a value receiver would copy chunks + logicalRowMap slice headers on every
+// compare (pair/isNull/cell), which is measurable on large n log n sorts.
+func (b *physicalColumnBase) pair(i, j uint64) (arrI, arrJ arrow.Array, li, lj int) {
+ if len(b.chunks) == 1 {
+ arrI = b.chunks[0]
+ arrJ = arrI
+ li = int(i)
+ lj = int(j)
+ return
+ }
+ ci, li2, cj, lj2 := b.rowMap.pair(i, j)
+ arrI = b.chunks[ci]
+ arrJ = b.chunks[cj]
+ li, lj = li2, lj2
+ return
+}
+
+func (b *physicalColumnBase) isNullAtGlobal(row uint64) bool {
+ if len(b.chunks) == 1 {
+ return b.chunks[0].IsNull(int(row))
+ }
+ ci, li := b.rowMap.at(row)
+ return b.chunks[ci].IsNull(li)
+}
+
+func (b *physicalColumnBase) cell(row uint64) (ch arrow.Array, li int) {
+ if len(b.chunks) == 1 {
+ return b.chunks[0], int(row)
+ }
+ ci, li := b.rowMap.at(row)
+ return b.chunks[ci], li
+}
+
+func (b *physicalColumnBase) columnHasValidityNulls() bool { return b.validityNulls }
+
+// --- Monomorphic comparators (one concrete *array type each; mirrors C++ ConcreteColumnComparator<T>) ---
+
+type physicalSortInt8Column struct{ base physicalColumnBase }
+
+func newPhysicalSortInt8Column(chunks []arrow.Array, numRows int, vn bool) *physicalSortInt8Column {
+ return &physicalSortInt8Column{base: newPhysicalColumnBase(chunks, numRows, vn)}
+}
+
+func (c *physicalSortInt8Column) compareRowsForKey(i, j uint64, key SortKey) int {
+ ai, aj, li, lj := c.base.pair(i, j)
+ a := ai.(*array.Int8)
+ b := aj.(*array.Int8)
+ if c.base.validityNulls {
+ if v, stop := compareKeyedNulls(a.IsNull(li), b.IsNull(lj), key); stop {
+ return v
+ }
+ }
+ return compareOrdered(key.Order, a.Value(li), b.Value(lj))
+}
+
+func (c *physicalSortInt8Column) isNullAt(row uint64) bool { return c.base.isNullAtGlobal(row) }
+func (c *physicalSortInt8Column) hasNullLikeValues() bool { return false }
+func (c *physicalSortInt8Column) isNullLikeAt(uint64) bool { return false }
+func (c *physicalSortInt8Column) columnHasValidityNulls() bool {
+ return c.base.columnHasValidityNulls()
+}
Review Comment:
can't we use go generics here and just embed the base?
i.e.
```go
type physicalSortColumn[T arrow.ValueTypes] struct { physicalColumnBase }
...
func (c *physicalSortColumn[T]) compareRowsForKey(i, j uint64, key SortKey) int {
ai, aj, li, lj := c.pair(i, j)
a := ai.(arrow.TypedArray[T])
b := aj.(arrow.TypedArray[T])
if c.validityNulls {
if v, stop := compareKeyedNulls(a.IsNull(li), b.IsNull(lj), key); stop {
return v
}
}
return compareOrdered(key.Order, a.Value(li), b.Value(lj))
}
func (c *physicalSortColumn[T]) isNullAt(row uint64) bool { return c.isNullAtGlobal(row) }
```
etc.
##########
arrow/compute/internal/kernels/vector_sort_support.go:
##########
@@ -0,0 +1,211 @@
+// 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.
+
+//go:build go1.18
+
+// Support for vector_sort.go: ordering primitives for Apache Arrow compute sort semantics
+// (CompareTypeValues-style helpers).
+//
+// Sort compares logical rows in random order (stable_sort / merge). For multi-chunk columns,
+// a dense logical-row→(chunk, offset) table gives O(1) per compare (faster here than
+// ChunkResolver under random access). Single-chunk columns skip the table entirely.
+
+package kernels
+
+import (
+ "bytes"
+ "cmp"
+
+ "github.com/apache/arrow-go/v18/arrow"
+ "github.com/apache/arrow-go/v18/arrow/float16"
+)
+
+// logicalRowMap is a precomputed map from logical row index to chunk index and in-chunk offset.
+// One struct per row (not two parallel int slices) so chunk/local live in the same cache line and
+// pair(i,j) touches two contiguous cells instead of four scattered int loads.
+type rowMapCell struct {
+ chunk int
+ local int
+}
+
+type logicalRowMap struct {
+ cells []rowMapCell
+}
+
+func newLogicalRowMap(chunks []arrow.Array, numRows int) logicalRowMap {
+ cells := make([]rowMapCell, numRows)
+ g := 0
+ for ci, arr := range chunks {
+ for li := 0; li < arr.Len(); li++ {
+ cells[g] = rowMapCell{chunk: ci, local: li}
+ g++
+ }
+ }
+ return logicalRowMap{cells: cells}
+}
+
+func (m *logicalRowMap) at(global uint64) (chunk, local int) {
+ c := m.cells[global]
+ return c.chunk, c.local
+}
+
+// pair resolves two logical rows in one call (hot path for compare); avoids double bounds/setup vs two at()s.
+func (m *logicalRowMap) pair(i, j uint64) (ci, li, cj, lj int) {
+ ai := m.cells[i]
+ aj := m.cells[j]
+ return ai.chunk, ai.local, aj.chunk, aj.local
+}
+
+func totalChunkRows(chunks []arrow.Array) (sum int) {
+ for _, c := range chunks {
+ sum += c.Len()
+ }
+ return sum
+}
+
+func chunksHaveNulls(chunks []arrow.Array) bool {
+ for _, ch := range chunks {
+ if ch.NullN() != 0 {
+ return true
+ }
+ }
+ return false
+}
+
+func compareOrdered[T cmp.Ordered](order SortOrder, vi, vj T) int {
+ c := cmp.Compare(vi, vj)
+ if order == Descending {
+ return -c
+ }
+ return c
+}
+
+func compareBytesOrdered(order SortOrder, vi, vj []byte) int {
+ c := bytes.Compare(vi, vj)
+ if order == Descending {
+ return -c
+ }
+ return c
+}
+
+func compareBoolOrdered(order SortOrder, vi, vj bool) int {
+ var c int
+ switch {
+ case !vi && vj:
+ c = -1
+ case vi && !vj:
+ c = 1
+ default:
+ c = 0
+ }
+ if order == Descending {
+ return -c
+ }
+ return c
+}
+
+func compareFloatNaNs(order SortOrder, viNaN, vjNaN bool) (int, bool) {
+ if viNaN && vjNaN {
+ return 0, true
+ }
+ if viNaN {
+ if order == Ascending {
+ return 1, true
+ }
+ return -1, true
+ }
+ if vjNaN {
+ if order == Ascending {
+ return -1, true
+ }
+ return 1, true
+ }
+ return 0, false
+}
+
+func sortFloat64[T float16.Num | float32 | float64](v T) float64 {
+ switch x := any(v).(type) {
+ case float16.Num:
+ return float64(x.Float32())
+ case float32:
+ return float64(x)
+ case float64:
+ return x
+ default:
+ panic("kernels: unreachable sortFloat64 type")
+ }
+}
+
+func compareKeyedNulls(nullI, nullJ bool, key SortKey) (cmpVal int, stop bool) {
+ if nullI && nullJ {
+ return 0, true
+ }
+ if nullI {
+ if key.NullPlacement == NullsAtStart {
+ return -1, true
+ }
+ return 1, true
+ }
+ if nullJ {
+ if key.NullPlacement == NullsAtStart {
+ return 1, true
+ }
+ return -1, true
+ }
+ return 0, false
+}
+
+func compareCmperOrdered[T interface{ Cmp(T) int }](order SortOrder, vi, vj T) int {
+ c := vi.Cmp(vj)
+ if order == Descending {
+ return -c
+ }
+ return c
+}
+
+func compareDayTimeOrdered(order SortOrder, vi, vj arrow.DayTimeInterval) int {
Review Comment:
would it make more sense to add a `Cmp` method to these types instead of defining them separately?
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org