DuckDB/SQL 窗口聚合执行

复用区间聚合状态计算 SQL 窗口

DuckDB 为适用的窗口聚合建立 16 叉线段树，将每个窗口分解为少量区间并合并已计算的聚合状态。

v1.2.1检索与计算核验 2026-10-12

工程问题#

SQL 窗口函数要为许多行计算不同范围的聚合值。例如窗口范围相互重叠时，逐行重新扫描整个范围会重复处理相同输入。实现还需要支持不同聚合函数，而不能只对可做前缀差分的求和使用专门公式。

实际实现#

WindowAggregateExecutor 在其他专用路径不适用时选择 WindowSegmentTree。叶层对应输入行，内层保存连续区间的聚合状态，v1.2.1 的分支数为 16。求值将窗口范围逐层拆成边缘片段与完整组，完整组复用内层状态，通过聚合函数的 combine 合并；边缘输入通过 update 加入，并按向量批次执行。

处理流程#

根据窗口聚合的语义选择适用执行器
每 16 个连续输入或下层状态合成一个父层状态
把当前窗口范围按树层级分解，定位完整组及两侧边缘
内层状态调用 combine，叶层输入调用 update
完成批量合并后由聚合函数生成结果

源码片段#

固定版本 · 原文摘录

src/function/window/window_aggregate_function.cppv1.2.1 · L55–L73

查看原文件

55	// Force naive for SEPARATE mode or for (currently!) unsupported functionality56	if (!ClientConfig::GetConfig(context).enable_optimizer || mode == WindowAggregationMode::SEPARATE) {57		aggregator = make_uniq<WindowNaiveAggregator>(*this, shared);58	} else if (WindowDistinctAggregator::CanAggregate(wexpr)) {59		// build a merge sort tree60		// see https://dl.acm.org/doi/pdf/10.1145/3514221.352618461		aggregator = make_uniq<WindowDistinctAggregator>(wexpr, shared, context);62	} else if (WindowConstantAggregator::CanAggregate(wexpr)) {63		aggregator = make_uniq<WindowConstantAggregator>(wexpr, shared, context);64	} else if (WindowCustomAggregator::CanAggregate(wexpr, mode)) {65		aggregator = make_uniq<WindowCustomAggregator>(wexpr, shared);66	} else if (WindowSegmentTree::CanAggregate(wexpr)) {67		// build a segment tree for frame-adhering aggregates68		// see http://www.vldb.org/pvldb/vol8/p1058-leis.pdf69		aggregator = make_uniq<WindowSegmentTree>(wexpr, shared);70	} else {71		// No accelerator can handle this combination, so fall back to naïve.72		aggregator = make_uniq<WindowNaiveAggregator>(*this, shared);73	}

WindowAggregateExecutor::WindowAggregateExecutor

线段树只是实际执行器选择的一条分支；DISTINCT、常量、自定义或不受支持的组合会选择其他实现。

CPPMIT

src/function/window/window_segment_tree.cppv1.2.1 · L37–L55

查看原文件

37	//! The owning aggregator38	const WindowSegmentTree &tree;39	//! The actual window segment tree: an array of aggregate states that represent all the intermediate nodes40	WindowAggregateStates levels_flat_native;41	//! For each level, the starting location in the levels_flat_native array42	vector<idx_t> levels_flat_start;43	//! The level being built (read)44	std::atomic<idx_t> build_level;45	//! The number of entries started so far at each level46	unique_ptr<AtomicCounters> build_started;47	//! The number of entries completed so far at each level48	unique_ptr<AtomicCounters> build_completed;49	//! The tree allocators.50	//! We need to hold onto them for the tree lifetime,51	//! not the lifetime of the local state that constructed part of the tree52	vector<unique_ptr<ArenaAllocator>> tree_allocators;5354	// TREE_FANOUT needs to cleanly divide STANDARD_VECTOR_SIZE55	static constexpr idx_t TREE_FANOUT = 16;

WindowSegmentTreeGlobalState

内层状态存放在扁平数组，各层记录起始偏移；这个版本明确使用 16 叉结构，不是教科书中固定二叉的表示。

CPPMIT

src/function/window/window_segment_tree.cppv1.2.1 · L376–L382

查看原文件

376		// compute the aggregate for this entry in the segment tree377		const idx_t pos = build_idx * gstate.TREE_FANOUT;378		const idx_t levels_flat_offset = levels_flat_start[level_current] + build_idx;379		auto state_ptr = levels_flat_native.GetStatePtr(levels_flat_offset);380		gtstate.WindowSegmentValue(gstate, level_current, pos, MinValue(level_size, pos + gstate.TREE_FANOUT),381		                           state_ptr);382		gtstate.FlushStates(level_current > 0);

WindowSegmentTreeState::Finalize

取一组最多 TREE_FANOUT 个下层条目，调用同一套区间聚合逻辑构建父层状态，并根据层数选择 update 或 combine。

CPPMIT

src/function/window/window_segment_tree.cppv1.2.1 · L519–L540

查看原文件

519			if (parent_begin == parent_end) {520				if (l_idx) {521					WindowSegmentValue(tree, l_idx, begin, end, state_ptr);522				}523				break;524			}525			idx_t group_begin = parent_begin * tree.TREE_FANOUT;526			if (begin != group_begin) {527				if (l_idx) {528					WindowSegmentValue(tree, l_idx, begin, group_begin + tree.TREE_FANOUT, state_ptr);529				}530				parent_begin++;531			}532			idx_t group_end = parent_end * tree.TREE_FANOUT;533			if (end != group_end) {534				if (l_idx) {535					if (order_insensitive) {536						WindowSegmentValue(tree, l_idx, group_end, end, state_ptr);537					} else {538						right_stack[l_idx] = {group_end, end};539						right_max = l_idx;540					}

WindowSegmentTreePart::EvaluateUpperLevels

范围被分解为同父组内片段及两侧不完整组；完整中间部分继续向上层处理，顺序敏感聚合把右侧片段暂存以保持顺序。

CPPMIT

src/function/window/window_segment_tree.cppv1.2.1 · L194–L210

查看原文件

194void WindowSegmentTreePart::FlushStates(bool combining) {195	if (!flush_count) {196		return;197	}198199	AggregateInputData aggr_input_data(aggr.GetFunctionData(), allocator);200	if (combining) {201		statel.Verify(flush_count);202		aggr.function.combine(statel, statep, aggr_input_data, flush_count);203	} else {204		auto &scanned = cursor->chunk;205		leaves.Slice(scanned, filter_sel, flush_count);206		aggr.function.update(&leaves.data[0], aggr_input_data, leaves.ColumnCount(), statep, flush_count);207	}208209	flush_count = 0;210}