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

Method SortInternal

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

Source from the content-addressed store, hash-verified

647 }
648
649 Status SortInternal() {
650 // Sort each batch independently and merge to sorted indices.
651 const int64_t num_batches = static_cast<int64_t>(batches_.size());
652 if (num_batches == 0) {
653 return Status::OK();
654 }
655 std::vector<NullLikePartition> sorted(num_batches);
656
657 // First sort all individual batches
658 int64_t begin_offset = 0;
659 int64_t end_offset = 0;
660 for (int64_t i = 0; i < num_batches; ++i) {
661 const auto& batch = *batches_[i];
662 end_offset += batch.num_rows();
663 RadixRecordBatchSorter sorter(
664 {indices_.data() + begin_offset, indices_.data() + end_offset}, batch,
665 options_);
666 ARROW_ASSIGN_OR_RAISE(sorted[i], sorter.Sort(begin_offset));
667 DCHECK_EQ(sorted[i].overall_begin(), indices_.data() + begin_offset);
668 DCHECK_EQ(sorted[i].overall_end(), indices_.data() + end_offset);
669 DCHECK_EQ(
670 static_cast<int64_t>(sorted[i].non_null_like_range.size() +
671 sorted[i].nan_range.size() + sorted[i].null_range.size()),
672 batch.num_rows());
673 begin_offset = end_offset;
674 }
675 DCHECK_EQ(end_offset, static_cast<int64_t>(indices_.size()));
676
677 // Then merge them by pairs, recursively
678 if (sorted.size() > 1) {
679 ChunkedIndexMapper chunked_mapper(batches_, indices_);
680 ARROW_ASSIGN_OR_RAISE(auto chunked_indices, chunked_mapper.LogicalToPhysical());
681
682 std::vector<ChunkedNullLikePartition> chunk_sorted(num_batches);
683 for (int64_t i = 0; i < num_batches; ++i) {
684 chunk_sorted[i] = sorted[i].TranslateTo(indices_, chunked_indices);
685 }
686
687 struct Visitor {
688 TableSorter* sorter;
689 std::vector<ChunkedNullLikePartition>* chunk_sorted;
690
691#define VISIT(TYPE) \
692 Status Visit(const TYPE& type) { return sorter->MergeInternal<TYPE>(chunk_sorted); }
693
694 VISIT_SORTABLE_PHYSICAL_TYPES(VISIT)
695 VISIT(NullType)
696#undef VISIT
697
698 Status Visit(const DataType& type) {
699 return Status::NotImplemented("Unsupported type for sorting: ",
700 type.ToString());
701 }
702 };
703 Visitor visitor{this, &chunk_sorted};
704 RETURN_NOT_OK(VisitTypeInline(*sort_keys_[0].type, &visitor));
705
706 DCHECK_EQ(chunk_sorted.size(), 1);

Callers

nothing calls this directly

Calls 11

VisitTypeInlineFunction · 0.85
overall_beginMethod · 0.80
overall_endMethod · 0.80
TranslateToMethod · 0.80
PhysicalToLogicalMethod · 0.80
OKFunction · 0.50
ARROW_ASSIGN_OR_RAISEFunction · 0.50
sizeMethod · 0.45
num_rowsMethod · 0.45
dataMethod · 0.45
SortMethod · 0.45

Tested by

no test coverage detected