Skip to content

Commit af9dad5

Browse files
authored
[feature](be) Support spill for non-streaming window functions (#68500)
### What problem does this PR solve? Issue Number: None Related PR: None Problem Summary: Large non-streaming window partitions currently retain all input blocks until the partition closes. A sufficiently large partition can therefore exhaust BE memory even when query spill is enabled. This change adds a capability-gated spill path for eligible non-streaming window functions: - keeps genuinely streaming windows on the existing in-memory path; - incrementally detects partition boundaries and stores the original input blocks in a batch store; - reduces full-partition aggregates while collecting input, and spills input blocks on memory revocation, on a configurable threshold, or in forced-spill mode; - records bounded peer-group metadata for `percent_rank` and `cume_dist`, with independent metadata spill; - publishes all partitions that end inside one input block as a single `AnalyticSpillBatch` (per-partition row ends, reduce results and ntile parameters; batch-relative peer group ends), so high-cardinality partition keys do not create per-partition descriptors, aggregate-state rebuilds or 1-row output blocks; - after a batch is spilled, coalesces small blocks into a write buffer and writes them once it reaches `spill_buffer_size_bytes`, flushing it on revoke and seal; - replays batches from the source operator in `batch_size` slices and tracks peer-group metadata with the query MemTracker; the source reserves replay memory only for the spilled files it is about to read (data file and peer-group sidecar of the queued batch, and the next data or sidecar record during replay), so in-memory batches are consumed without a disk-read reservation; - fills peer-function results once per peer/output intersection and checks cancellation before each fill, without fixed 4096-row splits; - keeps a sealed batch in memory unless it reaches `spill_analytic_sink_mem_limit_bytes`, so batches are not written to disk without memory pressure; - preserves the existing path when any function or frame is unsupported; - adds `spill_analytic_sink_mem_limit_bytes` and window-spill profile counters. The initial supported set is: - full-partition `sum`/`sum0`/`count`/`avg` and fixed-length-state `min`/`max`, including `OVER ()` / `OVER (PARTITION BY ...)` without ORDER BY, which Nereids plans as `RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW` with no order-by expressions (every row is a peer, so the frame is the whole partition); - `ntile` with `ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`; - `percent_rank` and `cume_dist` with `RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`. The new source file shifts the BE unity batches so that `async_result_writer.cpp` shares a translation unit with a file that includes `local_exchanger.h`. Both declare `clear_blocks` with a default argument, which fails with "redefinition of default argument"; the redeclaration in `async_result_writer.cpp` no longer repeats the default argument (its only call passes both arguments). Performance (5M unique partition keys, `sum(v) over (partition by k)`, SQL/query cache off): 0.14s with spill enabled vs 0.26s on the in-memory path; the source emits ~4K rows per block. Coalescing spill writes (50M narrow rows, `spill_analytic_sink_mem_limit_bytes=1MB`, `sum(v) over ()`): spill blocks 6152 -> 96, serialize time 958ms -> 388ms, spill file 38MB -> 11.8MB, query 1.81s -> 1.26s. TPC-DS SF10000 (single BE, `exec_mem_limit=8GB`): full-partition aggregates, ntile, percent_rank/cume_dist over `store_sales` (28.8B rows) and a 930M-row single partition all completed with the window sink peak at about 64MB per instance; 2.4B ticket-level partitions ran entirely through in-memory batches. ### Release note Eligible non-streaming window functions can spill partitions to local storage when query spill is enabled. ### Check List (For Author) - Test - [x] Regression test - New `spill_p0/window_function_spill`: 12 queries (full-partition aggregates with an all-NULL partition, skew, no partition, high cardinality, ntile, percent_rank/cume_dist, unsupported fallback, streaming) each run with spill disabled, spill enabled and forced spill; all three outputs are identical. - [x] Unit Test - Earlier full-suite run: `ENABLE_UNITY_BUILD=ON ./run-be-ut.sh --run --filter='AnalyticSinkOperatorTest.*:BoundaryPoseTest.*'` — 38/38 passed under ASAN, including write coalescing, replay slicing, revoke flush, peer-group sidecar files, replay reservation for in-memory / data-only / data-plus-sidecar batches and sidecar records read during replay, and the proactive spill limit. - Earlier full build: `./build.sh --be --fe` — passed. - `build-support/check-format.sh`, `build-support/check-build-hygiene.sh`, `git diff --check` — passed. - [x] Manual test - Profiles confirm `sum(v) over ()` spilling 5M rows and `partition by k` using in-memory batches. - A TPC-DS style validation (store/ticket/date partitions compared with GROUP BY references) passed on a local scaled-down dataset with and without spill. - [ ] No need to test or manual test. Explain why: - [ ] This is a refactor/code format and no logic has been changed. - [ ] Previous test can cover this change. - [ ] No code files have been changed. - [ ] Other reason Validation notes: Latest follow-up (`a225ec4bd70`): - Peer replay checks cancellation before each peer/output fill; output is already bounded by `batch_size`, so there is no extra 4096-row split. - Added focused unit cases for cancellation before filling a large peer, filling a large peer in one iteration, and cancellation between uneven peers. - `BUILD_TYPE=ASAN ENABLE_UNITY_BUILD=ON ./build.sh --be -j16` — passed. - `ENABLE_UNITY_BUILD=ON ./run-be-ut.sh --run --filter='AnalyticSinkOperatorTest.Spill*' -j16` — the changed production and test translation units compiled, but the test executable could not be rebuilt/run because of existing `be/test/exprs/function/function_string_test.cpp:2971-2987` compilation errors (`Field` string construction and removed `FunctionContext` scope values). The earlier 38/38 result above does not cover this follow-up. - `build-support/clang-format.sh`, `build-support/check-format.sh`, `build-support/check-build-hygiene.sh`, and `git diff --check` — passed. - SQL regression was not rerun for this cancellation-check refactoring. - Clang-tidy cannot fully run on the local toolchain (`stddef.h` not found); reported diagnostics on the touched files are pre-existing cognitive-complexity warnings or false positives from the failed parse. - Behavior changed: - [ ] No. - [x] Yes. Eligible non-streaming analytic partitions can spill; streaming and unsupported windows retain the existing behavior. - Does this need documentation? - [x] No. The implementation design is included in this PR; no user-facing documentation change is required for this initial version. - [ ] Yes. ### Check List (For Reviewer who merge this PR) - [ ] Confirm the release note - [ ] Confirm test cases - [ ] Confirm document - [ ] Add branch pick label https://claude.ai/code/session_01J4WRvR5E8wQd6ew3LsJoAt
1 parent c00ecb1 commit af9dad5

29 files changed

Lines changed: 5356 additions & 25 deletions

‎be/src/core/pod_array.h‎

Lines changed: 8 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -152,7 +152,7 @@ class PODArrayBase : private boost::noncopyable,
152152
}
153153

154154
void alloc_for_num_elements(size_t num_elements) {
155-
alloc(round_up_to_power_of_two_or_zero(minimum_memory_for_elements(num_elements)));
155+
alloc(allocated_bytes_for_elements(num_elements));
156156
}
157157

158158
template <typename... TAllocatorParams>
@@ -240,6 +240,11 @@ class PODArrayBase : private boost::noncopyable,
240240
#endif
241241

242242
public:
243+
/// Allocation size when creating storage for num_elements, including padding and rounding.
244+
static size_t allocated_bytes_for_elements(size_t num_elements) {
245+
return round_up_to_power_of_two_or_zero(minimum_memory_for_elements(num_elements));
246+
}
247+
243248
bool empty() const { return c_end == c_start; }
244249
size_t size() const { return (c_end - c_start) / ELEMENT_SIZE; }
245250
size_t capacity() const { return (c_end_of_storage - c_start) / ELEMENT_SIZE; }
@@ -257,7 +262,7 @@ class PODArrayBase : private boost::noncopyable,
257262
template <typename... TAllocatorParams>
258263
void reserve(size_t n, TAllocatorParams&&... allocator_params) {
259264
if (n > capacity())
260-
realloc(round_up_to_power_of_two_or_zero(minimum_memory_for_elements(n)),
265+
realloc(allocated_bytes_for_elements(n),
261266
std::forward<TAllocatorParams>(allocator_params)...);
262267
}
263268

@@ -690,4 +695,4 @@ void swap(PODArray<T, initial_bytes, TAllocator, pad_right_, pad_left_>& lhs,
690695
}
691696

692697
} // namespace doris
693-
#include "common/compile_check_avoid_end.h"
698+
#include "common/compile_check_avoid_end.h"

‎be/src/exec/operator/analytic_sink_operator.cpp‎

Lines changed: 674 additions & 13 deletions
Large diffs are not rendered by default.

‎be/src/exec/operator/analytic_sink_operator.h‎

Lines changed: 76 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -18,10 +18,11 @@
1818

1919
#pragma once
2020

21-
#include <stdint.h>
22-
2321
#include <algorithm>
22+
#include <cstdint>
2423

24+
#include "core/custom_allocator.h"
25+
#include "exec/operator/analytic_spill.h"
2526
#include "exec/operator/operator.h"
2627
#include "exec/pipeline/dependency.h"
2728

@@ -62,16 +63,19 @@ class PartitionStatistics {
6263
// those function cacluate need partition info, so can't be used in streaming mode
6364
static const std::set<std::string> PARTITION_FUNCTION_SET {"ntile", "cume_dist", "percent_rank"};
6465

65-
class AnalyticSinkLocalState : public PipelineXSinkLocalState<AnalyticSharedState> {
66+
class AnalyticSinkLocalState : public PipelineXSpillSinkLocalState<AnalyticSharedState> {
6667
ENABLE_FACTORY_CREATOR(AnalyticSinkLocalState);
6768

6869
public:
70+
using Base = PipelineXSpillSinkLocalState<AnalyticSharedState>;
71+
6972
AnalyticSinkLocalState(DataSinkOperatorXBase* parent, RuntimeState* state)
70-
: PipelineXSinkLocalState<AnalyticSharedState>(parent, state) {}
73+
: Base(parent, state) {}
7174

7275
Status init(RuntimeState* state, LocalSinkStateInfo& info) override;
7376
Status open(RuntimeState* state) override;
7477
Status close(RuntimeState* state, Status exec_status) override;
78+
bool is_blockable() const override;
7579

7680
private:
7781
enum class RowsWindowType { NONE, UNBOUNDED_START, SLIDING };
@@ -107,6 +111,38 @@ class AnalyticSinkLocalState : public PipelineXSinkLocalState<AnalyticSharedStat
107111
void _destroy_agg_status();
108112
void _remove_unused_rows();
109113

114+
void _init_spill_mode(const AnalyticSinkOperatorX& parent);
115+
Status _sink_spill(RuntimeState* state, Block* input_block, bool eos);
116+
Status _process_spill_block(RuntimeState* state, Block* input_block);
117+
Status _finish_spill_sink_call(RuntimeState* state, bool eos);
118+
Status _materialize_spill_columns(Block* input_block,
119+
std::vector<std::vector<ColumnPtr>>* agg_columns,
120+
std::vector<ColumnPtr>* partition_columns,
121+
std::vector<ColumnPtr>* order_columns);
122+
Status _append_spill_rows(RuntimeState* state, Block* input_block, size_t start, size_t length);
123+
Status _accumulate_spill_range(RuntimeState* state,
124+
const std::vector<std::vector<ColumnPtr>>& agg_columns,
125+
const std::vector<ColumnPtr>& order_columns, size_t start,
126+
size_t length, int64_t batch_row);
127+
void _update_spill_aggregate_states(size_t start, size_t length,
128+
const std::vector<std::vector<ColumnPtr>>& agg_columns);
129+
Status _record_peer_groups(RuntimeState* state, const std::vector<ColumnPtr>& order_columns,
130+
size_t start, size_t length, int64_t batch_row);
131+
Status _finish_spill_partition(RuntimeState* state);
132+
Status _seal_spill_batch(RuntimeState* state);
133+
Status _spill_batch_store(RuntimeState* state);
134+
void _ensure_spill_batch_store();
135+
static void _save_last_keys(const std::vector<ColumnPtr>& columns, size_t row,
136+
std::vector<ColumnPtr>& last_keys);
137+
bool _keys_equal(const std::vector<ColumnPtr>& lhs, size_t lhs_row,
138+
const std::vector<ColumnPtr>& rhs, size_t rhs_row) const;
139+
Status _find_spill_boundary(RuntimeState* state, const std::vector<ColumnPtr>& columns,
140+
size_t start, size_t end, const PartitionStatistics& statistics,
141+
size_t* boundary) const;
142+
Status _find_spill_partition_starts(RuntimeState* state, const std::vector<ColumnPtr>& columns,
143+
size_t rows, std::vector<size_t>* partition_starts);
144+
void _update_spill_memory_usage();
145+
110146
void _get_partition_by_end();
111147
void _find_next_partition_ends();
112148
void _update_order_by_range();
@@ -175,8 +211,34 @@ class AnalyticSinkLocalState : public PipelineXSinkLocalState<AnalyticSharedStat
175211
RuntimeProfile::Counter* _remove_count = nullptr;
176212
RuntimeProfile::Counter* _remove_rows = nullptr;
177213
RuntimeProfile::HighWaterMarkCounter* _blocks_memory_usage = nullptr;
214+
RuntimeProfile::Counter* _spilled_partitions = nullptr;
215+
RuntimeProfile::Counter* _in_memory_partitions = nullptr;
216+
RuntimeProfile::Counter* _max_partition_rows = nullptr;
217+
RuntimeProfile::HighWaterMarkCounter* _peak_partition_buffered_bytes = nullptr;
218+
RuntimeProfile::Counter* _peer_group_metadata_bytes = nullptr;
178219

179220
int64_t _reserve_mem_size = 0;
221+
222+
bool _spill_enabled = false;
223+
bool _has_peer_group_functions = false;
224+
std::vector<WindowSpillStrategy> _spill_strategies;
225+
// NTILE bucket counts, indexed by function index. Initialized from the first nonempty input
226+
// and copied into each sealed batch; other strategies leave their entries at zero.
227+
DorisVector<int64_t> _spill_ntile_bucket_counts;
228+
// Rows of the batch that has not been handed to the source yet. Finished partitions are only
229+
// kept here while one input Block is processed; afterwards it holds at most the open partition.
230+
std::unique_ptr<AnalyticSpillBatchStore> _batch_store;
231+
// Rows and exclusive batch-relative end row of the partition that is still receiving rows.
232+
int64_t _open_partition_rows = 0;
233+
int64_t _open_partition_end = 0;
234+
// Batch-relative start of the open peer group, including rows from preceding input Blocks.
235+
int64_t _open_peer_group_start = 0;
236+
// Metadata of the finished partitions in _batch_store, moved into AnalyticSpillBatch on seal.
237+
std::vector<int64_t> _batch_partition_ends;
238+
MutableColumns _batch_partition_results;
239+
std::vector<ColumnPtr> _last_partition_keys;
240+
std::vector<ColumnPtr> _last_order_keys;
241+
size_t _batch_buffered_bytes = 0;
180242
};
181243

182244
class AnalyticSinkOperatorX final : public DataSinkOperatorX<AnalyticSinkLocalState> {
@@ -229,11 +291,17 @@ class AnalyticSinkOperatorX final : public DataSinkOperatorX<AnalyticSinkLocalSt
229291

230292
bool is_colocated_operator() const override { return _is_colocate; }
231293
bool is_shuffled_operator() const override { return !_partition_by_eq_expr_ctxs.empty(); }
294+
bool is_blockable(RuntimeState* state) const override;
232295

233296
size_t get_reserve_mem_size(RuntimeState* state, bool eos) override;
297+
size_t get_reserve_mem_size(RuntimeState* state, bool eos, const Block* block) override;
298+
size_t revocable_mem_size(RuntimeState* state) const override;
299+
Status revoke_memory(RuntimeState* state) override;
234300

235301
private:
236302
friend class AnalyticSinkLocalState;
303+
304+
void _prepare_spill(RuntimeState* state);
237305
Status _insert_range_column(Block* block, const VExprContextSPtr& expr, IColumn* dst_column,
238306
size_t length);
239307
Status _add_input_block(doris::RuntimeState* state, Block* input_block);
@@ -262,6 +330,10 @@ class AnalyticSinkOperatorX final : public DataSinkOperatorX<AnalyticSinkLocalSt
262330
bool _has_range_window;
263331
bool _has_window_start;
264332
bool _has_window_end;
333+
bool _enable_spill_analytic = false;
334+
std::string _window_spill_unsupported_reason;
335+
std::vector<WindowSpillStrategy> _window_spill_strategies;
336+
std::vector<WindowSpillPeerFunction> _window_spill_peer_functions;
265337

266338
/// The offset of the n-th functions.
267339
std::vector<size_t> _offsets_of_aggregate_states;

0 commit comments

Comments
 (0)