DuckDB/ORDER BY · 本地排序块

按字节排序 ORDER BY 的定长键

DuckDB 将排序键组织为可按字节比较的表示，定长短键用 LSD 基数排序，每轮通过计数和累计偏移稳定分配行。

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

工程问题#

数据库 ORDER BY 需要反复比较多个列并同步重排行。对于定长键，若每次比较都解读数据类型、空值和排序方向，会在大量行排序中重复执行这些工作。

实际实现#

PhysicalOrder 收集排序键与 payload，LocalSortState 生成本地有序块。RadixSort 根据输入选择实现；不含字符串、记录数超过短数组阈值且键宽不超过 LSD 阈值时，RadixSortLSD 从最低有效字节到最高字节逐轮统计计数、计算累计位置，再从后向前稳定散布记录。这里搬运的排序记录包含序列化键和行索引，完整 payload 在之后按排序结果重排。

处理流程#

ORDER BY 计算键表达式并把键与 payload 送入本地排序状态
按键类型、记录数和键宽选择 LSD 路径
统计当前字节的 256 种取值并累计各桶结束位置
从后向前按桶位置写入目标缓冲区，保持相同字节的原相对次序
交换读写缓冲区，继续上一字节；排序块随后参与合并

源码片段#

固定版本 · 原文摘录

src/execution/operator/order/physical_order.cppv1.1.3 · L86–L103

查看原文件

86	// Obtain sorting columns87	auto &keys = lstate.keys;88	keys.Reset();89	lstate.key_executor.Execute(chunk, keys);9091	auto &payload = lstate.payload;92	payload.ReferenceColumns(chunk, projections);9394	// Sink the data into the local sort state95	keys.Verify();96	chunk.Verify();97	local_sort_state.SinkChunk(keys, payload);9899	// When sorting data reaches a certain size, we sort it100	if (local_sort_state.SizeInBytes() >= gstate.memory_per_thread) {101		local_sort_state.Sort(global_sort_state, true);102	}103	return SinkResultType::NEED_MORE_INPUT;

PhysicalOrder::Sink

ORDER BY 求出键、收集 payload，并在本地数据达到线程内存额度时调用排序。

CPPMIT

src/common/sort/sort_state.cppv1.1.3 · L237–L258

查看原文件

237void LocalSortState::Sort(GlobalSortState &global_sort_state, bool reorder_heap) {238	D_ASSERT(radix_sorting_data->count == payload_data->count);239	if (radix_sorting_data->count == 0) {240		return;241	}242	// Move all data to a single SortedBlock243	sorted_blocks.emplace_back(make_uniq<SortedBlock>(*buffer_manager, global_sort_state));244	auto &sb = *sorted_blocks.back();245	// Fixed-size sorting data246	auto sorting_block = ConcatenateBlocks(*radix_sorting_data);247	sb.radix_sorting_data.push_back(std::move(sorting_block));248	// Variable-size sorting data249	if (!sort_layout->all_constant) {250		auto &blob_data = *blob_sorting_data;251		auto new_block = ConcatenateBlocks(blob_data);252		sb.blob_sorting_data->data_blocks.push_back(std::move(new_block));253	}254	// Payload data255	auto payload_block = ConcatenateBlocks(*payload_data);256	sb.payload_data->data_blocks.push_back(std::move(payload_block));257	// Now perform the actual sort258	SortInMemory();

LocalSortState::Sort → SortInMemory

把已有行数据整理为本地排序块，随后调用 SortInMemory。

CPPMIT

src/common/sort/radix_sort.cppv1.1.3 · L305–L324

查看原文件

305	for (idx_t i = 0; i < sort_layout->column_count; i++) {306		sorting_size += sort_layout->column_sizes[i];307		contains_string = contains_string || sort_layout->logical_types[i].InternalType() == PhysicalType::VARCHAR;308		if (sort_layout->constant_size[i] && i < sort_layout->column_count - 1) {309			// Add columns to the sorting size until we reach a variable size column, or the last column310			continue;311		}312313		if (!ties) {314			// This is the first sort315			RadixSort(*buffer_manager, dataptr, count, col_offset, sorting_size, *sort_layout, contains_string);316			ties_ptr = make_unsafe_uniq_array_uninitialized<bool>(count);317			ties = ties_ptr.get();318			std::fill_n(ties, count - 1, true);319			ties[count - 1] = false;320		} else {321			// For subsequent sorts, we only have to subsort the tied tuples322			SubSortTiedTuples(*buffer_manager, dataptr, count, col_offset, sorting_size, ties, *sort_layout,323			                  contains_string);324		}

LocalSortState::SortInMemory → RadixSort

累积排序列的键宽并记录是否包含字符串；首次排序调用 RadixSort，后续仅处理仍相等的记录。

CPPMIT

src/common/sort/radix_sort.cppv1.1.3 · L238–L255

查看原文件

238//! Calls different sort functions, depending on the count and sorting sizes239void RadixSort(BufferManager &buffer_manager, const data_ptr_t &dataptr, const idx_t &count, const idx_t &col_offset,240               const idx_t &sorting_size, const SortLayout &sort_layout, bool contains_string) {241242	if (contains_string) {243		auto begin = duckdb_pdqsort::PDQIterator(dataptr, sort_layout.entry_size);244		auto end = begin + count;245		duckdb_pdqsort::PDQConstants constants(sort_layout.entry_size, col_offset, sorting_size, *end);246		return duckdb_pdqsort::pdqsort_branchless(begin, begin + count, constants);247	}248249	if (count <= SortConstants::INSERTION_SORT_THRESHOLD) {250		return InsertionSort(dataptr, nullptr, count, col_offset, sort_layout.entry_size, sorting_size, 0, false);251	}252253	if (sorting_size <= SortConstants::MSD_RADIX_SORT_SIZE_THRESHOLD) {254		return RadixSortLSD(buffer_manager, dataptr, count, col_offset, sort_layout.entry_size, sorting_size);255	}

RadixSort：算法选择

实际选择条件是字符串、行数和键宽；最后展示 LSD 分支，较宽键的 MSD 分支紧接其后。

CPPMIT

src/common/sort/radix_sort.cppv1.1.3 · L115–L134

查看原文件

115	idx_t counts[SortConstants::VALUES_PER_RADIX];116	for (idx_t r = 1; r <= sorting_size; r++) {117		// Init counts to 0118		memset(counts, 0, sizeof(counts));119		// Const some values for convenience120		const data_ptr_t source_ptr = swap ? temp_block.get() : dataptr;121		const data_ptr_t target_ptr = swap ? dataptr : temp_block.get();122		const idx_t offset = col_offset + sorting_size - r;123		// Collect counts124		data_ptr_t offset_ptr = source_ptr + offset;125		for (idx_t i = 0; i < count; i++) {126			counts[*offset_ptr]++;127			offset_ptr += row_width;128		}129		// Compute offsets from counts130		idx_t max_count = counts[0];131		for (idx_t val = 1; val < SortConstants::VALUES_PER_RADIX; val++) {132			max_count = MaxValue<idx_t>(max_count, counts[val]);133			counts[val] = counts[val] + counts[val - 1];134		}

RadixSortLSD：逐字节计数

由低位字节向前推进，统计当前字节的频率，再把计数转换为累计结束位置。

CPPMIT

src/common/sort/radix_sort.cppv1.1.3 · L135–L151

查看原文件

135		if (max_count == count) {136			continue;137		}138		// Re-order the data in temporary array139		data_ptr_t row_ptr = source_ptr + (count - 1) * row_width;140		for (idx_t i = 0; i < count; i++) {141			idx_t &radix_offset = --counts[*(row_ptr + offset)];142			FastMemcpy(target_ptr + radix_offset * row_width, row_ptr, row_width);143			row_ptr -= row_width;144		}145		swap = !swap;146	}147	// Move data back to original buffer (if it was swapped)148	if (swap) {149		memcpy(dataptr, temp_block.get(), count * row_width);150	}151}