Skip to content

Commit ffb9e72

Browse files
HappenLeelihaopeng
andcommitted
[Sort] Support merge sort in ExchangeNode (apache#19)
Change-Id: I5f15771153fe8e982c78c581c42d5b1e25ab543f Co-authored-by: lihaopeng <[email protected]>
1 parent 53788df commit ffb9e72

9 files changed

Lines changed: 342 additions & 26 deletions

‎be/src/vec/CMakeLists.txt‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -85,6 +85,7 @@ set(VEC_FILES
8585
runtime/vdata_stream_recvr.cpp
8686
runtime/vdata_stream_mgr.cpp
8787
runtime/vpartition_info.cpp
88+
runtime/vsorted_run_merger.cpp
8889
)
8990

9091
add_library(Vec STATIC

‎be/src/vec/core/sort_cursor.h‎

Lines changed: 49 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,7 @@
77
#include "vec/core/column_numbers.h"
88
#include "vec/columns/column.h"
99
#include "vec/columns/column_string.h"
10+
#include "vec/exprs/vexpr_context.h"
1011
#include "vec/runtime/vdata_stream_recvr.h"
1112

1213
namespace doris::vectorized
@@ -86,35 +87,69 @@ struct SortCursorImpl
8687
: column_desc.column_number;
8788
sort_columns.push_back(columns[column_number].get());
8889

89-
need_collation[j] = desc[j].collator != nullptr && typeid_cast<const ColumnString *>(sort_columns.back()); /// TODO Nullable(String)
90-
has_collation |= need_collation[j];
90+
// need_collation[j] = desc[j].collator != nullptr && typeid_cast<const ColumnString *>(sort_columns.back()); /// TODO Nullable(String)
91+
// has_collation |= need_collation[j];
9192
}
9293

9394
pos = 0;
9495
rows = all_columns[0]->size();
9596
}
9697

9798
bool isFirst() const { return pos == 0; }
98-
virtual bool isLast() { return pos + 1 >= rows; }
99+
bool isLast() { return pos + 1 >= rows; }
99100
void next() { ++pos; }
101+
102+
virtual bool has_next_block() { return false; }
103+
virtual Block* block_ptr() { return nullptr; }
100104
};
101105

106+
using BlockSupplier = std::function<Status(Block **)>;
107+
102108
struct ReceiveQueueSortCursorImpl : public SortCursorImpl {
103-
ReceiveQueueSortCursorImpl() = default;
104-
VDataStreamRecvr::SenderQueue* _sender_queue;
105-
106-
bool isLast() override {
107-
if (pos + 1 >= rows) {
108-
Block* block_ptr;
109-
auto status = _sender_queue->get_batch(&block_ptr);
110-
if (status.ok() && block_ptr != nullptr) {
111-
SortCursorImpl::reset(*block_ptr);
112-
} else {
113-
return true;
109+
ReceiveQueueSortCursorImpl(const BlockSupplier& block_supplier, const std::vector<VExprContext*>& ordering_expr, const std::vector<bool>& is_asc_order,
110+
const std::vector<bool>& nulls_first):
111+
SortCursorImpl(), _ordering_expr(ordering_expr), _block_supplier(block_supplier){
112+
sort_columns_size = ordering_expr.size();
113+
114+
desc.resize(ordering_expr.size());
115+
for (int i = 0; i < desc.size(); i++) {
116+
desc[i].direction = is_asc_order[i] ? 1 : -1;
117+
desc[i].nulls_direction = nulls_first[i] ? 1 : -1;
118+
}
119+
has_next_block();
120+
}
121+
122+
bool has_next_block() override {
123+
auto status = _block_supplier(&_block_ptr);
124+
if (status.ok() && _block_ptr != nullptr) {
125+
for (int i = 0; i < desc.size(); ++i) {
126+
_ordering_expr[i]->execute(_block_ptr, &desc[i].column_number);
114127
}
128+
SortCursorImpl::reset(*_block_ptr);
129+
return true;
115130
}
131+
_block_ptr = nullptr;
116132
return false;
117133
}
134+
135+
Block* block_ptr() override {
136+
return _block_ptr;
137+
}
138+
139+
size_t columns_num() const { return all_columns.size(); }
140+
141+
Block create_empty_blocks() const {
142+
size_t num_columns = columns_num();
143+
MutableColumns columns(num_columns);
144+
for (size_t i = 0; i < num_columns; ++i)
145+
columns[i] = all_columns[i]->cloneEmpty();
146+
return _block_ptr->cloneWithColumns(std::move(columns));
147+
}
148+
149+
const std::vector<VExprContext*>& _ordering_expr;
150+
Block* _block_ptr = nullptr;
151+
BlockSupplier _block_supplier{};
152+
bool _is_eof = false;
118153
};
119154

120155
/// For easy copying.

‎be/src/vec/exec/vexchange_node.cpp‎

Lines changed: 8 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@ namespace doris::vectorized {
99
VExchangeNode::VExchangeNode(ObjectPool* pool, const TPlanNode& tnode, const DescriptorTbl& descs)
1010
: ExecNode(pool, tnode, descs),
1111
_num_senders(0),
12+
_offset(tnode.exchange_node.__isset.offset ? tnode.exchange_node.offset : 0),
1213
_is_merging(tnode.exchange_node.__isset.sort_info),
1314
_stream_recvr(nullptr) {}
1415

@@ -43,7 +44,13 @@ Status VExchangeNode::prepare(RuntimeState* state) {
4344
Status VExchangeNode::open(RuntimeState* state) {
4445
SCOPED_TIMER(_runtime_profile->total_time_counter());
4546
RETURN_IF_ERROR(ExecNode::open(state));
46-
// TODO: sort
47+
48+
if (_is_merging) {
49+
RETURN_IF_ERROR(_vsort_exec_exprs.open(state));
50+
RETURN_IF_ERROR(_stream_recvr->create_merger(_vsort_exec_exprs.lhs_ordering_expr_ctxs(),
51+
_is_asc_order, _nulls_first, state->batch_size(), _limit, _offset));
52+
}
53+
4754
return Status::OK();
4855
}
4956
Status VExchangeNode::get_next(RuntimeState* state, RowBatch* row_batch, bool* eos) {

‎be/src/vec/exec/vexchange_node.h‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -34,6 +34,7 @@ class VExchangeNode : public ExecNode {
3434
std::shared_ptr<QueryStatisticsRecvr> _sub_plan_query_statistics_recvr;
3535

3636
// use in merge sort
37+
size_t _offset;
3738
VSortExecExprs _vsort_exec_exprs;
3839
std::vector<bool> _is_asc_order;
3940
std::vector<bool> _nulls_first;

‎be/src/vec/exec/vsort_node.cpp‎

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -72,10 +72,9 @@ Status VSortNode::open(RuntimeState* state) {
7272
}
7373

7474
Status VSortNode::get_next(RuntimeState* state, RowBatch* row_batch, bool* eos) {
75-
// return Status::NotSupported("Not Implemented VSortNode::get_next scalar");
76-
// row_batch = nullptr;
75+
row_batch = nullptr;
7776
*eos = true;
78-
return Status::OK();
77+
return Status::NotSupported("Not Implemented VSortNode::get_next scalar");
7978
}
8079

8180
Status VSortNode::get_next(RuntimeState* state, Block* block, bool* eos) {

‎be/src/vec/runtime/vdata_stream_recvr.cpp‎

Lines changed: 29 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -3,8 +3,11 @@
33
#include "gen_cpp/data.pb.h"
44
#include "runtime/mem_tracker.h"
55
#include "util/uid_util.h"
6+
67
#include "vec/core/block.h"
8+
#include "vec/core/sort_cursor.h"
79
#include "vec/runtime/vdata_stream_mgr.h"
10+
#include "vec/runtime/vsorted_run_merger.h"
811

912
namespace doris::vectorized {
1013

@@ -219,6 +222,21 @@ VDataStreamRecvr::~VDataStreamRecvr() {
219222
DCHECK(_mgr == nullptr) << "Must call close()";
220223
}
221224

225+
Status VDataStreamRecvr::create_merger(const std::vector<VExprContext*>& ordering_expr, const std::vector<bool>& is_asc_order,
226+
const std::vector<bool>& nulls_first, const size_t batch_size, int64_t limit, size_t offset) {
227+
DCHECK(_is_merging);
228+
vector<BlockSupplier> child_block_suppliers;
229+
// Create the merger that will a single stream of sorted rows.
230+
_merger.reset(new VSortedRunMerger(ordering_expr, is_asc_order, nulls_first, batch_size, limit, offset, _profile));
231+
232+
for (int i = 0; i < _sender_queues.size(); ++i) {
233+
child_block_suppliers.emplace_back(
234+
std::bind(std::mem_fn(&SenderQueue::get_batch), _sender_queues[i], std::placeholders::_1));
235+
}
236+
RETURN_IF_ERROR(_merger->prepare(child_block_suppliers));
237+
return Status::OK();
238+
}
239+
222240
void VDataStreamRecvr::add_batch(const PBlock& pblock, int sender_id, int be_number,
223241
int64_t packet_seq, ::google::protobuf::Closure** done) {
224242
int use_sender_id = _is_merging ? sender_id : 0;
@@ -229,12 +247,18 @@ Status VDataStreamRecvr::get_next(Block* block, bool* eos) {
229247
// TODO: use merge
230248
block->clear();
231249
Block* res = nullptr;
232-
RETURN_IF_ERROR(_sender_queues[0]->get_batch(&res));
233-
if (res != nullptr) {
234-
*block = *res;
250+
251+
if (!_is_merging) {
252+
RETURN_IF_ERROR(_sender_queues[0]->get_batch(&res));
253+
if (res != nullptr) {
254+
*block = *res;
255+
} else {
256+
*eos = true;
257+
}
235258
} else {
236-
*eos = true;
259+
RETURN_IF_ERROR(_merger->get_next(block, eos));
237260
}
261+
238262
return Status::OK();
239263
}
240264

@@ -258,8 +282,7 @@ void VDataStreamRecvr::close() {
258282
_mgr->deregister_recvr(fragment_instance_id(), dest_node_id());
259283
_mgr = nullptr;
260284

261-
// TODO:
262-
// _merger.reset();
285+
_merger.reset();
263286
// TODO: Maybe shared tracker doesn't need to be reset manually
264287
_mem_tracker.reset();
265288
}

‎be/src/vec/runtime/vdata_stream_recvr.h‎

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,9 @@ class PBlock;
2626
namespace vectorized {
2727
class Block;
2828
class VDataStreamMgr;
29+
class VSortedRunMerger;
30+
class VExprContext;
31+
2932
class VDataStreamRecvr {
3033
public:
3134
VDataStreamRecvr(VDataStreamMgr* stream_mgr, const std::shared_ptr<MemTracker>& parent_tracker,
@@ -36,7 +39,8 @@ class VDataStreamRecvr {
3639

3740
~VDataStreamRecvr();
3841

39-
// TODO: merger
42+
Status create_merger(const std::vector<VExprContext*>& ordering_expr, const std::vector<bool>& is_asc_order,
43+
const std::vector<bool>& nulls_first, const size_t batch_size, int64_t limit, size_t offset);
4044

4145
void add_batch(const PBlock& pblock, int sender_id, int be_number, int64_t packet_seq,
4246
::google::protobuf::Closure** done);
@@ -92,7 +96,8 @@ class VDataStreamRecvr {
9296
std::shared_ptr<MemTracker> _mem_tracker;
9397
std::vector<SenderQueue*> _sender_queues;
9498

95-
// TODO: declare merger
99+
std::unique_ptr<VSortedRunMerger> _merger;
100+
96101
ObjectPool _sender_queue_pool;
97102
RuntimeProfile* _profile;
98103

Lines changed: 147 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,147 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
#include "vec/runtime/vsorted_run_merger.h"
19+
20+
#include <vector>
21+
22+
#include "exprs/expr.h"
23+
#include "runtime/descriptors.h"
24+
#include "runtime/row_batch.h"
25+
#include "runtime/sorter.h"
26+
#include "runtime/tuple_row.h"
27+
#include "util/debug_util.h"
28+
#include "util/defer_op.h"
29+
#include "util/runtime_profile.h"
30+
31+
using std::vector;
32+
33+
namespace doris::vectorized {
34+
35+
VSortedRunMerger::VSortedRunMerger(const std::vector<VExprContext *>& ordering_expr, const std::vector<bool>& is_asc_order,
36+
const std::vector<bool>& nulls_first, const size_t batch_size, int64_t limit, size_t offset, RuntimeProfile* profile)
37+
:_ordering_expr(ordering_expr), _is_asc_order(is_asc_order), _nulls_first(nulls_first), _batch_size(batch_size),
38+
_limit(limit), _offset(offset){
39+
_get_next_timer = ADD_TIMER(profile, "MergeGetNext");
40+
_get_next_batch_timer = ADD_TIMER(profile, "MergeGetNextBatch");
41+
}
42+
43+
Status VSortedRunMerger::prepare(const vector<BlockSupplier>& input_runs, bool parallel) {
44+
for (const auto &supplier : input_runs) {
45+
_cursors.emplace_back(supplier, _ordering_expr, _is_asc_order, _nulls_first);
46+
}
47+
48+
for (size_t i = 0; i < _cursors.size(); ++i) {
49+
_priority_queue.push(SortCursor(&_cursors[i]));
50+
}
51+
52+
for (const auto& cursor : _cursors) {
53+
if (!cursor._is_eof) {
54+
_empty_block = cursor.create_empty_blocks();
55+
break;
56+
}
57+
}
58+
59+
return Status::OK();
60+
}
61+
62+
Status VSortedRunMerger::get_next(Block* output_block, bool* eos) {
63+
// Only have one receive data queue of data, no need to do merge and
64+
// copy the data of block.
65+
// return the data in receive data directly
66+
if (_priority_queue.size() == 1) {
67+
auto current = _priority_queue.top();
68+
while (_offset != 0 && current->block_ptr() != nullptr) {
69+
if (_offset >= current->rows - current->pos) {
70+
_offset -= (current->rows - current->pos);
71+
current->has_next_block();
72+
} else {
73+
current->pos += _offset;
74+
_offset = 0;
75+
}
76+
}
77+
78+
if (current->isFirst()) {
79+
if (current->block_ptr() != nullptr) {
80+
current->block_ptr()->swap(*output_block);
81+
*eos = !current->has_next_block();
82+
} else {
83+
*eos = true;
84+
}
85+
} else {
86+
if (current->block_ptr() != nullptr) {
87+
for (int i = 0; i < current->all_columns.size(); i++) {
88+
auto& column_with_type = current->block_ptr()->getByPosition(i);
89+
column_with_type.column = column_with_type.column->cut(current->pos,
90+
current->rows - current->pos);
91+
}
92+
current->block_ptr()->swap(*output_block);
93+
*eos = !current->has_next_block();
94+
} else {
95+
*eos = true;
96+
}
97+
}
98+
} else {
99+
size_t num_columns = _empty_block.columns();
100+
MutableColumns merged_columns = _empty_block.cloneEmptyColumns();
101+
/// TODO: reserve (in each column)
102+
103+
/// Take rows from queue in right order and push to 'merged'.
104+
size_t merged_rows = 0;
105+
while (!_priority_queue.empty()) {
106+
auto current = _priority_queue.top();
107+
_priority_queue.pop();
108+
109+
if (_offset > 0) {
110+
_offset--;
111+
} else {
112+
for (size_t i = 0; i < num_columns; ++i)
113+
merged_columns[i]->insertFrom(*current->all_columns[i], current->pos);
114+
++merged_rows;
115+
}
116+
next_heap(current);
117+
if (merged_rows == _batch_size)
118+
break;
119+
}
120+
121+
if (merged_rows == 0) {
122+
*eos = true;
123+
return Status::OK();
124+
}
125+
126+
Block merge_block = _empty_block.cloneWithColumns(std::move(merged_columns));
127+
merge_block.swap(*output_block);
128+
}
129+
130+
_num_rows_returned += output_block->rows();
131+
if (_limit != -1 && _num_rows_returned >= _limit) {
132+
output_block->set_num_rows(output_block->rows() - (_num_rows_returned - _limit));
133+
*eos = true;
134+
}
135+
return Status::OK();
136+
}
137+
138+
void VSortedRunMerger::next_heap(SortCursor& current) {
139+
if (!current->isLast()) {
140+
current->next();
141+
_priority_queue.push(current);
142+
} else if (current->has_next_block()) {
143+
_priority_queue.push(current);
144+
}
145+
}
146+
147+
} // namespace doris

0 commit comments

Comments
 (0)