MCPcopy Create free account
hub / github.com/apache/arrow / SortInternal

Method SortInternal

cpp/src/arrow/compute/kernels/vector_sort.cc:81–171  ·  view source on GitHub ↗

Source from the content-addressed store, hash-verified

79 private:
80 template <typename Type>
81 Status SortInternal() {
82 using ArrayType = typename TypeTraits<Type>::ArrayType;
83 ArraySortOptions options(order_, null_placement_);
84 const auto num_chunks = static_cast<int>(physical_chunks_.size());
85 if (num_chunks == 0) {
86 DCHECK_EQ(static_cast<int64_t>(indices_.size()), 0);
87 *output_ = NullLikePartition::FromCounts(indices_, 0, 0, 0, null_placement_);
88 return Status::OK();
89 }
90 const int64_t num_indices = static_cast<int64_t>(indices_.size());
91 const auto arrays = GetArrayPointers(physical_chunks_);
92
93 // Sort each chunk independently and merge to sorted indices.
94 // This is a serial implementation.
95 std::vector<NullLikePartition> sorted(num_chunks);
96
97 // First sort all individual chunks
98 int64_t begin_offset = 0;
99 int64_t non_null_like_count = 0;
100 for (int i = 0; i < num_chunks; ++i) {
101 const auto array = checked_cast<const ArrayType*>(arrays[i]);
102 const auto array_length = array->length();
103 ARROW_ASSIGN_OR_RAISE(
104 sorted[i], array_sorter_(indices_.subspan(begin_offset, array_length), *array,
105 begin_offset, options, ctx_));
106 non_null_like_count += sorted[i].non_null_like_range.size();
107 begin_offset += array_length;
108 }
109 DCHECK_EQ(begin_offset, num_indices);
110
111 // Then merge them by pairs, recursively
112 if (sorted.size() > 1) {
113 ChunkedIndexMapper chunked_mapper(arrays, indices_);
114 ARROW_ASSIGN_OR_RAISE(auto chunked_indices, chunked_mapper.LogicalToPhysical());
115
116 std::vector<ChunkedNullLikePartition> chunk_sorted(num_chunks);
117 for (int i = 0; i < num_chunks; ++i) {
118 chunk_sorted[i] = sorted[i].TranslateTo(indices_, chunked_indices);
119 }
120
121 // merge function for merging ranges where the first sort key is equal
122 // -> no-op because we have only one sort key
123 auto merge_remaining_sort_keys = [&](std::span<CompressedChunkLocation> range,
124 size_t middle,
125 CompressedChunkLocation* temp_indices) {};
126
127 auto merge_non_nulls = [&](std::span<CompressedChunkLocation> range, size_t middle,
128 CompressedChunkLocation* temp_indices) {
129 MergeNonNulls<ArrayType>(range.subspan(0, middle), range.subspan(middle), arrays,
130 {temp_indices, range.size()});
131 };
132
133 ChunkedMergeImpl merge_impl{null_placement_, std::move(merge_remaining_sort_keys),
134 std::move(merge_non_nulls)};
135 // std::merge is only called on non-null-like values, so size temp indices
136 // accordingly
137 RETURN_NOT_OK(merge_impl.Init(ctx_, non_null_like_count));
138

Callers

nothing calls this directly

Calls 15

GetArrayPointersFunction · 0.85
TranslateToMethod · 0.80
overall_endMethod · 0.80
overall_beginMethod · 0.80
resizeMethod · 0.80
PhysicalToLogicalMethod · 0.80
OKFunction · 0.50
ARROW_ASSIGN_OR_RAISEFunction · 0.50
sizeMethod · 0.45
lengthMethod · 0.45
InitMethod · 0.45
beginMethod · 0.45

Tested by

no test coverage detected