DuckDB Sort实现调查 | Mox的笔记库

目前DuckDB两个版本的Sort均是由Laurens Kuiper（Software Developer at DuckDB Labs and Ph.D. Student in the Database Architectures group at CWI.）写的

因此DuckDB的Sort分为两个文件夹

在src/common目录下，有sort和sorting文件夹

v1.4.0的排序方法位于sorting目录下（具体方法则位于third_party/ska_sort，third_party/verge_sort，third_party/pdq_sort下面），对应的状态管理是

1
class SortLocalSinkState;
2
class SortGlobalSinkState;
3
class SortLocalSourceState;
4
class SortGlobalSourceState;

而v1.4.0之前的排序方法位于sort目录下，对应的状态管理是

1
struct GlobalSortState
2
struct LocalSortState

调研主要以TPC-H Q1为主，结合Debug版本的编译与GDB，观察程序的实际执行路径

1
SELECT
2
    l_returnflag,
3
    l_linestatus,
4
    sum(l_quantity) AS sum_qty,
5
    sum(l_extendedprice) AS sum_base_price,
6
    sum(l_extendedprice * (1 - l_discount)) AS sum_disc_price,
7
    sum(l_extendedprice * (1 - l_discount) * (1 + l_tax)) AS sum_charge,
8
    avg(l_quantity) AS avg_qty,
9
    avg(l_extendedprice) AS avg_price,
10
    avg(l_discount) AS avg_disc,
11
    count(*) AS count_order
12
FROM
13
    lineitem
14
WHERE
15
    l_shipdate <= CAST('1998-09-02' AS date)
16
GROUP BY
17
    l_returnflag,
18
    l_linestatus
19
ORDER BY
20
    l_returnflag,
21
    l_linestatus;

最后结果的Aggregate分成4组，结果应该是下面情况

在PhysicalPlanGenerator::CreatePlan中，会将逻辑计划中的OrderBy转为物理计划，我们GDB从这里开始切入

1
case LogicalOperatorType::LOGICAL_ORDER_BY:
2
    return CreatePlan(op.Cast<LogicalOrder>());

前置知识

Key与Payload

Key为排序键（参与排序的数据），Payload则是不参与排序的数据

分离存储：key数据和payload数据分别存储在不同的集合中
指针关联：通过在排序键中存储payload的指针来建立关联
类型特化：针对不同的排序键类型(固定16字节、24字节、32字节、变长32字节等)进行优化
延迟绑定：在数据追加时立即建立key-payload关联，为后续排序做准备

如果是存在多个列需要Sort，就会把多列的数据组合为一行数据，这样排序只需要做一次（就是以行为单位做Sort）

DuckDB v1.4.0的做法

定义了新的枚举类SortKetyType

1
enum class SortKeyType : uint8_t {
2
  INVALID = 0,
3
  //! Without payload
4
  NO_PAYLOAD_FIXED_8 = 1,
5
  NO_PAYLOAD_FIXED_16 = 2,
6
  NO_PAYLOAD_FIXED_24 = 3,
7
  NO_PAYLOAD_FIXED_32 = 4,
8
  NO_PAYLOAD_VARIABLE_32 = 5,
9
  //! With payload (requires row pointer in key)
10
  PAYLOAD_FIXED_16 = 6,
11
  PAYLOAD_FIXED_24 = 7,
12
  PAYLOAD_FIXED_32 = 8,
13
  PAYLOAD_VARIABLE_32 = 9,
14
};

sort.cpp

Sort的运行函数如下：

对于orders，这是一个std::vector

运行Q1时orders.size()为2，与order by的列数一致

如果进一步检查其中的expressions，可以发现是l_returnflag和l_linestatus

orders.GetOrderModifieer()获取ASC和DESC

order.expression->return_type获取列的类型

将以上信息传入create_children，作为构成Key组合键的信息

通过binder.BindScalarFunction(DEFAULT_SCHEMA, "create_sort_key", std::move(create_children), error)生成reate_sort_key——对于Q1，进入LogicalTypeId::BIGINT分支

同时紧跟在这段代码后面，生成decode_sort_key

1
decode_sort_key->return_type = LogicalType::STRUCT(std::move(decode_child_list));

根据projection_map生成payload_layout(这是一种行存形式tupleDataLayout)和填充output_projection_columns

1
  vector<LogicalType> payload_types;
2
  for (idx_t output_col_idx = 0; output_col_idx < projection_map.size(); output_col_idx++) {
3
    const auto &input_col_idx = projection_map[output_col_idx];
4
    const auto it = input_column_to_key.find(input_col_idx);
5
    if (it != input_column_to_key.end()) {
6
      // Projected column also appears as a key, just reference it
7
      output_projection_columns.push_back({false, it->second, output_col_idx});
8
    } else {
9
      // Projected column does not appear as a key, add to payload layout
10
      output_projection_columns.push_back({true, payload_types.size(), output_col_idx});
11
      payload_types.push_back(input_types[input_col_idx]);
12
      input_projection_map.push_back(input_col_idx);
13
    }
14
  }
15
  payload_layout->Initialize(payload_types, TupleDataValidityType::CAN_HAVE_NULL_VALUES);

然后用std::sort对于输出用的project_column进行排序，将Key的那部分移动到vector的开头

1
  std::sort(output_projection_columns.begin(), output_projection_columns.end(),
2
            [](const SortProjectionColumn &lhs, const SortProjectionColumn &rhs) {
3
              if (lhs.is_payload == rhs.is_payload) {
4
                return lhs.layout_col_idx < rhs.layout_col_idx;
5
              }
6
              return lhs.is_payload < rhs.is_payload;
7
            });

完整代码如下

1
Sort::Sort(ClientContext &context, const vector<BoundOrderByNode> &orders, const vector<LogicalType> &input_types,
2
           vector<idx_t> projection_map, bool is_index_sort_p)
3
    : key_layout(make_shared_ptr<TupleDataLayout>()), payload_layout(make_shared_ptr<TupleDataLayout>()),
4
      is_index_sort(is_index_sort_p) {
5
  // Convert orders to a single "create_sort_key" expression (and corresponding "decode_sort_key")
6
  FunctionBinder binder(context);
7
  vector<unique_ptr<Expression>> create_children;
8
  vector<unique_ptr<Expression>> decode_children;
9
  child_list_t<LogicalType> decode_child_list;
10
  for (idx_t col_idx = 0; col_idx < orders.size(); col_idx++) {
11
    const auto &order = orders[col_idx];
12

13
    // Create: for each column we have two arguments: 1. the column, 2. sort specifier
14
    create_children.emplace_back(order.expression->Copy());
15
    create_children.emplace_back(make_uniq<BoundConstantExpression>(Value(order.GetOrderModifier())));
16

17
    // Avoid having unnamed structs fields (otherwise we get a parser exception while binding)
18
    const auto col_name = StringUtil::Format("c%llu", col_idx);
19
    auto col_type = order.expression->return_type;
20
    decode_child_list.emplace_back(col_name, col_type);
21
    col_type = TypeVisitor::VisitReplace(col_type, [](const LogicalType &type) {
22
      if (type.id() != LogicalTypeId::STRUCT) {
23
        return type;
24
      }
25
      child_list_t<LogicalType> internal_child_list;
26
      for (const auto &child : StructType::GetChildTypes(type)) {
27
        internal_child_list.emplace_back(StringUtil::Format("c%llu", internal_child_list.size()), child.second);
28
      }
29
      return LogicalType::STRUCT(std::move(internal_child_list));
30
    });
31

32
    // Decode: for each column we have two arguments: 1. col name + type, 2. sort specifier
33
    decode_children.emplace_back(make_uniq<BoundConstantExpression>(Value(col_name + " " + col_type.ToString())));
34
    decode_children.emplace_back(make_uniq<BoundConstantExpression>(order.GetOrderModifier()));
35
  }
36

37
  ErrorData error;
38
  create_sort_key = binder.BindScalarFunction(DEFAULT_SCHEMA, "create_sort_key", std::move(create_children), error);
39
  if (!create_sort_key) {
40
    throw InternalException("Unable to bind create_sort_key in Sort::Sort");
41
  }
42

43
  switch (create_sort_key->return_type.id()) {
44
  case LogicalTypeId::BIGINT:
45
    decode_children.insert(decode_children.begin(),
46
                           make_uniq<BoundReferenceExpression>(LogicalType::BIGINT, static_cast<storage_t>(0)));
47
    break;
48
  default:
49
    D_ASSERT(create_sort_key->return_type.id() == LogicalTypeId::BLOB);
50
    decode_children.insert(decode_children.begin(),
51
                           make_uniq<BoundReferenceExpression>(LogicalType::BLOB, static_cast<storage_t>(0)));
52
  }
53

54
  decode_sort_key = binder.BindScalarFunction(DecodeSortKeyFun::GetFunction(), std::move(decode_children));
55
  if (!decode_sort_key) {
56
    throw InternalException("Unable to bind decode_sort_key in Sort::Sort");
57
  }
58

59
  // A bit hacky, but this way we make sure that the output does contain the unnamed structs again
60
  decode_sort_key->return_type = LogicalType::STRUCT(std::move(decode_child_list));
61

62
  // For convenience, we fill the projection map if it is empty
63
  if (projection_map.empty()) {
64
    projection_map.reserve(input_types.size());
65
    for (idx_t col_idx = 0; col_idx < input_types.size(); col_idx++) {
66
      projection_map.push_back(col_idx);
67
    }
68
  }
69

70
  // We need to output this many columns, reserve
71
  output_projection_columns.reserve(projection_map.size());
72

73
  // Create mapping from input column to key (so we won't duplicate columns in key/payload)
74
  unordered_map<idx_t, idx_t> input_column_to_key;
75
  for (idx_t key_idx = 0; key_idx < orders.size(); key_idx++) {
76
    const auto &key_order_expr = *orders[key_idx].expression;
77
    if (key_order_expr.GetExpressionClass() == ExpressionClass::BOUND_REF) {
78
      input_column_to_key.emplace(key_order_expr.Cast<BoundReferenceExpression>().index, key_idx);
79
    }
80
  }
81

82
  // Construct payload layout (excluding columns that also appear as key)
83
  vector<LogicalType> payload_types;
84
  for (idx_t output_col_idx = 0; output_col_idx < projection_map.size(); output_col_idx++) {
85
    const auto &input_col_idx = projection_map[output_col_idx];
86
    const auto it = input_column_to_key.find(input_col_idx);
87
    if (it != input_column_to_key.end()) {
88
      // Projected column also appears as a key, just reference it
89
      output_projection_columns.push_back({false, it->second, output_col_idx});
90
    } else {
91
      // Projected column does not appear as a key, add to payload layout
92
      output_projection_columns.push_back({true, payload_types.size(), output_col_idx});
93
      payload_types.push_back(input_types[input_col_idx]);
94
      input_projection_map.push_back(input_col_idx);
95
    }
96
  }
97
  payload_layout->Initialize(payload_types, TupleDataValidityType::CAN_HAVE_NULL_VALUES);
98

99
  // Sort the output projection columns so we're gathering the columns in order
100
  std::sort(output_projection_columns.begin(), output_projection_columns.end(),
101
            [](const SortProjectionColumn &lhs, const SortProjectionColumn &rhs) {
102
              if (lhs.is_payload == rhs.is_payload) {
103
                return lhs.layout_col_idx < rhs.layout_col_idx;
104
              }
105
              return lhs.is_payload < rhs.is_payload;
106
            });
107

108
  // Finally, initialize the key layout (now that we know whether we have a payload)
109
  key_layout->Initialize(orders, create_sort_key->return_type, !payload_types.empty());
110
}

最后单独生成key_layout

1
key_layout->Initialize(orders, create_sort_key->return_type, !payload_types.empty());

tuple_data_layout.cpp

根据参与排序键的属性，生成sort_width

对于Q1，这里的sort_width的最终结果为4（2+2），GetTypeIdSize(physical_type)得到的是1

1
if (TypeIsConstantSize(physical_type)) {
2
    // NULL byte + fixed-width type
3
    sort_width += 1 + GetTypeIdSize(physical_type);
4
} else if (logical_type == LogicalType::VARCHAR && order.stats &&
5
           StringStats::HasMaxStringLength(*order.stats)) {
6
    // NULL byte + maximum string length + string delimiter
7
    sort_width += 1 + StringStats::MaxStringLength(*order.stats) + 1;
8
} else {
9
    // We don't know how long the key will be
10
    sort_width = DConstants::INVALID_INDEX;
11
    break;
12
}

根据row_width选择SortKetyType，对于Q1，因为LogicalType是LogicalTypeId::BIGINT，所以初始值为8，因为有Payload所以再加8，最后sort_width 是16，由于有Payload，选择SortKeyType::PAYLOAD_FIXED_16

1
idx_t temp_row_width = type.id() == LogicalTypeId::BIGINT ? 8 : sort_width;
2
  if (sort_width != DConstants::INVALID_INDEX && has_payload) {
3
    temp_row_width += 8;
4
  }
5
  if (temp_row_width <= 8) {
6
    D_ASSERT(!has_payload);
7
    row_width = 8;
8
    sort_key_type = SortKeyType::NO_PAYLOAD_FIXED_8;
9
  } else if (temp_row_width <= 16) {
10
    row_width = 16;
11
    sort_key_type = has_payload ? SortKeyType::PAYLOAD_FIXED_16 : SortKeyType::NO_PAYLOAD_FIXED_16;
12
  } else if (temp_row_width <= 24) {
13
    row_width = 24;
14
    sort_key_type = has_payload ? SortKeyType::PAYLOAD_FIXED_24 : SortKeyType::NO_PAYLOAD_FIXED_24;
15
  } else if (temp_row_width <= 32) {
16
    row_width = 32;
17
    sort_key_type = has_payload ? SortKeyType::PAYLOAD_FIXED_32 : SortKeyType::NO_PAYLOAD_FIXED_32;
18
  } else {
19
    row_width = 32;
20
    sort_key_type = has_payload ? SortKeyType::PAYLOAD_VARIABLE_32 : SortKeyType::NO_PAYLOAD_VARIABLE_32;
21

22
    // Variable-size sort key, also set these properties
23
    all_constant = false;
24
    heap_size_offset = has_payload ? SortKey<SortKeyType::PAYLOAD_VARIABLE_32>::HEAP_SIZE_OFFSET
25
                                   : SortKey<SortKeyType::NO_PAYLOAD_VARIABLE_32>::HEAP_SIZE_OFFSET;
26
  }

sorted_run.cpp

在Sort算子的Sink阶段（可以理解为算子的执行与输出）如果有Payload，则需要给Payload设置相对应的Pointer

1
void SortedRun::Sink(DataChunk &key, DataChunk &payload) {
2
  D_ASSERT(!finalized);
3
  key_data->Append(key_append_state, key);
4
  if (payload_data) {
5
    D_ASSERT(key.size() == payload.size());
6
    payload_data->Append(payload_append_state, payload);
7
    SetPayloadPointer(key_append_state.chunk_state.row_locations, payload_append_state.chunk_state.row_locations,
8
                      key.size(), key_data->GetLayout().GetSortKeyType());
9
  }
10
}

通过SetPayloadPointer设置相对应的指针，根据sort_key_type找到相对应的模板生成(对于Q1，这里的count为4)

1
static void SetPayloadPointer(Vector &key_locations, Vector &payload_locations, const idx_t count,
2
                              const SortKeyType &sort_key_type) {
3
  switch (sort_key_type) {
4
  case SortKeyType::PAYLOAD_FIXED_16:
5
    return TemplatedSetPayloadPointer<SortKeyType::PAYLOAD_FIXED_16>(key_locations, payload_locations, count);
6
  case SortKeyType::PAYLOAD_FIXED_24:
7
    return TemplatedSetPayloadPointer<SortKeyType::PAYLOAD_FIXED_24>(key_locations, payload_locations, count);
8
  case SortKeyType::PAYLOAD_FIXED_32:
9
    return TemplatedSetPayloadPointer<SortKeyType::PAYLOAD_FIXED_32>(key_locations, payload_locations, count);
10
  case SortKeyType::PAYLOAD_VARIABLE_32:
11
    return TemplatedSetPayloadPointer<SortKeyType::PAYLOAD_VARIABLE_32>(key_locations, payload_locations, count);
12
  default:
13
    throw NotImplementedException("SetPayloadPointer for %s", EnumUtil::ToString(sort_key_type));
14
  }
15
}

可以看到模板设置的是指针

1
template <SortKeyType SORT_KEY_TYPE>
2
static void TemplatedSetPayloadPointer(Vector &key_locations, Vector &payload_locations, const idx_t count) {
3
  using SORT_KEY = SortKey<SORT_KEY_TYPE>;
4

5
  const auto key_locations_ptr = FlatVector::GetData<SORT_KEY *>(key_locations);
6
  const auto payload_locations_ptr = FlatVector::GetData<data_ptr_t>(payload_locations);
7

8
  for (idx_t i = 0; i < count; i++) {
9
    key_locations_ptr[i]->SetPayload(payload_locations_ptr[i]);
10
  }
11
}

SortSwitch判断KeyType类型，从模板转入对应Sort方法

1
static void SortSwitch(const TupleDataCollection &key_data, bool is_index_sort) {
2
  const auto sort_key_type = key_data.GetLayout().GetSortKeyType();
3
  switch (sort_key_type) {
4
  case SortKeyType::NO_PAYLOAD_FIXED_8:
5
    return TemplatedSort<SortKeyType::NO_PAYLOAD_FIXED_8>(key_data, is_index_sort);
6
  case SortKeyType::NO_PAYLOAD_FIXED_16:
7
    return TemplatedSort<SortKeyType::NO_PAYLOAD_FIXED_16>(key_data, is_index_sort);
8
  case SortKeyType::NO_PAYLOAD_FIXED_24:
9
    return TemplatedSort<SortKeyType::NO_PAYLOAD_FIXED_24>(key_data, is_index_sort);
10
  case SortKeyType::NO_PAYLOAD_FIXED_32:
11
    return TemplatedSort<SortKeyType::NO_PAYLOAD_FIXED_32>(key_data, is_index_sort);
12
  case SortKeyType::NO_PAYLOAD_VARIABLE_32:
13
    return TemplatedSort<SortKeyType::NO_PAYLOAD_VARIABLE_32>(key_data, is_index_sort);
14
  case SortKeyType::PAYLOAD_FIXED_16:
15
    return TemplatedSort<SortKeyType::PAYLOAD_FIXED_16>(key_data, is_index_sort);
16
  case SortKeyType::PAYLOAD_FIXED_24:
17
    return TemplatedSort<SortKeyType::PAYLOAD_FIXED_24>(key_data, is_index_sort);
18
  case SortKeyType::PAYLOAD_FIXED_32:
19
    return TemplatedSort<SortKeyType::PAYLOAD_FIXED_32>(key_data, is_index_sort);
20
  case SortKeyType::PAYLOAD_VARIABLE_32:
21
    return TemplatedSort<SortKeyType::PAYLOAD_VARIABLE_32>(key_data, is_index_sort);
22
  default:
23
    throw NotImplementedException("TemplatedSort for %s", EnumUtil::ToString(sort_key_type));
24
  }
25
}

在TemplatedSort当中，则默认使用vergesort，fallback时会选择ska_sort

1
const auto ska_sort_width = MinValue<idx_t>(layout.GetSortWidth(), sizeof(uint64_t));

对于Q1，这里的ska_sort_width为4，为计算前面的sort_width所得到的

完整代码如下：

1
  auto begin = BLOCK_ITERATOR(state, 0);
2
  auto end = BLOCK_ITERATOR(state, key_data.Count());
3

4
  const auto requires_next_sort =
5
      is_index_sort ? false : !SORT_KEY::CONSTANT_SIZE || SORT_KEY::INLINE_LENGTH != sizeof(uint64_t);
6
  const auto ska_sort_width = MinValue<idx_t>(layout.GetSortWidth(), sizeof(uint64_t));
7
  const auto &sort_skippable_bytes = layout.GetSortSkippableBytes();
8
  auto ska_extract_key =
9
      SkaExtractKey<SORT_KEY>(requires_next_sort, ska_sort_width, sort_skippable_bytes, context.interrupted);
10

11
  const auto fallback = [ska_extract_key](const BLOCK_ITERATOR &fb_begin, const BLOCK_ITERATOR &fb_end) {
12
    duckdb_ska_sort::ska_sort(fb_begin, fb_end, ska_extract_key);
13
  };
14
  duckdb_vergesort::vergesort(begin, end, std::less<SORT_KEY>(), fallback);

vergesort.h

对于verge_sort小于128个元素的数组，使用回退算法

而Q1需要排序的Aggregate分组只有4个（小于阈值24），所以直接fallback到ska_sort

1
if (dist < 128) {
2
    // Vergesort is inefficient for small collections
3
    fallback(first, last);
4
    return;
5
}

ska_sort.hpp

ska_sort内部则是inplace_radix_sort

1
template<typename It, typename ExtractKey>
2
static void ska_sort(It begin, It end, ExtractKey && extract_key)
3
{
4
    detail::inplace_radix_sort<128, 1024>(begin, end, extract_key);
5
}

对于Q1会掉入StdSortFallbacks，这里的fallback被设置成为了pdqsort_branchless，同时配置好comp函数

1
template<typename It, typename ExtractKey>
2
inline void StdSortFallback(It begin, It end, ExtractKey & extract_key)
3
{
4
  // LNK note that we use the full comparison (not just extracted key) here
5
    static const auto comp = [&](const typename std::remove_reference<decltype(*begin)>::type & l, const typename std::remove_reference<decltype(*begin)>::type & r){ return l < r; };
6
  static const auto fallback = [&](const It &fb_begin, const It &fb_end) {
7
    duckdb_pdqsort::pdqsort_branchless(fb_begin, fb_end, comp);
8
  };
9
  duckdb_vergesort::vergesort(begin, end, comp, fallback);
10
}

调用堆栈如下图

pdq_sort.h

Q1需要排序的Aggregate分组只有4个（小于阈值24），进入pdqsort_detail::pdqsort_loop

1
template<class Iter, class Compare>
2
inline void pdqsort_branchless(Iter begin, Iter end, Compare comp) {
3
    if (begin == end) return;
4
    pdqsort_detail::pdqsort_loop<Iter, Compare, true>(
5
        begin, end, comp, pdqsort_detail::log2(end - begin));
6
}

由于再次小于阈值24，所以进入insertion_sort

1
if (size < insertion_sort_threshold) {
2
    if (leftmost) insertion_sort(begin, end, comp);
3
    else unguarded_insertion_sort(begin, end, comp);
4
    return;
5
}

C++

1
    template<class Iter, class Compare>
2
    inline void insertion_sort(Iter begin, Iter end, Compare comp) {
3
        typedef typename std::iterator_traits<Iter>::value_type T;
4
        if (begin == end) return;
5

6
        for (Iter cur = begin + 1; cur != end; ++cur) {
7
            Iter sift = cur;
8
            Iter sift_1 = cur - 1;
9

10
            // Compare first so we can avoid 2 moves for an element already positioned correctly.
11
            if (comp(*sift, *sift_1)) {
12
                T tmp = PDQSORT_PREFER_MOVE(*sift);
13

14
                do { *sift-- = PDQSORT_PREFER_MOVE(*sift_1); }
15
                while (sift != begin && comp(tmp, *--sift_1));
16

17
                *sift = PDQSORT_PREFER_MOVE(tmp);
18
            }
19
        }
20
    }

DuckDB v1.4.0之前

我调试使用的是v1.3.2版本

状态管理默认的进入入口会是LocalSortState::SortInMemory()

对于这个版本，Sort会直接调用src/common/sort/radix_sort.cpp中的RadixSort

有意思的地方在于，虽然l_returnflag和l_linestatus是varchar，但contains_string这里值为false——实际调试显示l_returnflag和varchar被优化为Uint8

以及，虽然函数的名称为RadixSort，但也会根据排序组数选择不同算法

同样因为只有4组，小于阈值24，所以还是InsertationSort——但这个应该是Laurens Kuiper参考原版的PDQSort自己写的

1
if (count <= SortConstants::INSERTION_SORT_THRESHOLD) {
2
    return InsertionSort(dataptr, nullptr, count, col_offset, sort_layout.entry_size, sorting_size, 0, false);
3
  }

InsertationSort内部

1
inline void InsertionSort(const data_ptr_t orig_ptr, const data_ptr_t temp_ptr, const idx_t &count,
2
                          const idx_t &col_offset, const idx_t &row_width, const idx_t &total_comp_width,
3
                          const idx_t &offset, bool swap) {
4
  const data_ptr_t source_ptr = swap ? temp_ptr : orig_ptr;
5
  const data_ptr_t target_ptr = swap ? orig_ptr : temp_ptr;
6
  if (count > 1) {
7
    const idx_t total_offset = col_offset + offset;
8
    auto temp_val = make_unsafe_uniq_array_uninitialized<data_t>(row_width);
9
    const data_ptr_t val = temp_val.get();
10
    const auto comp_width = total_comp_width - offset;
11
    for (idx_t i = 1; i < count; i++) {
12
      FastMemcpy(val, source_ptr + i * row_width, row_width);
13
      idx_t j = i;
14
      while (j > 0 &&
15
             FastMemcmp(source_ptr + (j - 1) * row_width + total_offset, val + total_offset, comp_width) > 0) {
16
        FastMemcpy(source_ptr + j * row_width, source_ptr + (j - 1) * row_width, row_width);
17
        j--;
18
      }
19
      FastMemcpy(source_ptr + j * row_width, val, row_width);
20
    }
21
  }
22
  if (swap) {
23
    memcpy(target_ptr, source_ptr, count * row_width);
24
  }
25
}

DuckDB版RadixSort完整代码如下

1
void RadixSort(BufferManager &buffer_manager, const data_ptr_t &dataptr, const idx_t &count, const idx_t &col_offset,
2
               const idx_t &sorting_size, const SortLayout &sort_layout, bool contains_string) {
3

4
  if (contains_string) {
5
    auto begin = duckdb_pdqsort::PDQIterator(dataptr, sort_layout.entry_size);
6
    auto end = begin + count;
7
    duckdb_pdqsort::PDQConstants constants(sort_layout.entry_size, col_offset, sorting_size, *end);
8
    return duckdb_pdqsort::pdqsort_branchless(begin, begin + count, constants);
9
  }
10

11
  if (count <= SortConstants::INSERTION_SORT_THRESHOLD) {
12
    return InsertionSort(dataptr, nullptr, count, col_offset, sort_layout.entry_size, sorting_size, 0, false);
13
  }
14

15
  if (sorting_size <= SortConstants::MSD_RADIX_SORT_SIZE_THRESHOLD) {
16
    return RadixSortLSD(buffer_manager, dataptr, count, col_offset, sort_layout.entry_size, sorting_size);
17
  }
18

19
  const auto block_size = buffer_manager.GetBlockSize();
20
  auto temp_block =
21
      buffer_manager.Allocate(MemoryTag::ORDER_BY, MaxValue(count * sort_layout.entry_size, block_size));
22
  auto pre_allocated_array =
23
      make_unsafe_uniq_array_uninitialized<idx_t>(sorting_size * SortConstants::MSD_RADIX_LOCATIONS);
24
  RadixSortMSD(dataptr, temp_block.Ptr(), count, col_offset, sort_layout.entry_size, sorting_size, 0,
25
               pre_allocated_array.get(), false);
26
}

性能对比参照

New Sorting Implementation

这是DuckDB关于他们最新Sort的Pull Request解释，该版本用于最新的DuckDB V1.4.0中的order by——他们在PR中说明将会替换原有排序方式，并且在测试中有2倍以上的性能提升

Table	Column Type(s)	Rows [Millions]	Current [s]	New [s]	Speedup [x]
Ascending	1 `UBIGINT`	10	0.110	0.033	3.333
Ascending	1 `UBIGINT`	100	0.912	0.181	5.038
Ascending	1 `UBIGINT`	1000	15.302	1.475	10.374
Descending	1 `UBIGINT`	10	0.121	0.034	3.558
Descending	1 `UBIGINT`	100	0.908	0.207	4.386
Descending	1 `UBIGINT`	1000	15.789	1.712	9.222
Random	1 `UBIGINT`	10	0.120	0.094	1.276
Random	1 `UBIGINT`	100	1.028	0.587	1.751
Random	1 `UBIGINT`	1000	17.554	6.493	2.703
TPC-H SF1 l_comment	1 `VARCHAR`	~6	0.848	0.296	2.864
TPC-H SF 10 l_comment	1 `VARCHAR`	~60	8.465	3.090	2.739
TPC-H SF 100 l_comment	1 `VARCHAR`	~600	300+	35.187	8.525+
TPC-H SF 1 lineitem by l_shipdate	15 Mixed	~6	0.328	0.189	1.735
TPC-H SF 10 lineitem by l_shipdate	15 Mixed	~60	3.353	1.520	2.205
TPC-H SF 100 lineitem by l_shipdate	15 Mixed	~600	273.982	80.919	3.385

参考资料

第一个是DuckDB的官方博客，2和3是知乎上的分析，4是关于DuckDB Sort方法的论文（可以看到核心是PDQSort和RadixSort）——这些分析针对的是v1.4.0之前的情况

预计2025年9-10月DuckDB社区会有Blog说明v1.4.0的Sort的情况

Fastest Table Sort in the West – Redesigning DuckDB’s Sort

DuckDB的变长Sort实现

DuckDB Sort代码阅读和分析

ICDE2023-sorting.pdf

2021年Laurens Kuiper做的Sort重构：Rework physical ORDER BY

AI辅助解释

TupleDataLayout

TupleDataLayout 类详细解释

TupleDataLayout 是 DuckDB 中用于管理行数据布局的核心类，它定义了如何在内存中组织和存储元组（行）数据。

核心功能

1. 数据组织结构

TupleDataLayout 管理行数据的内存布局，包含以下组件：

有效性标志区域 (flag_width): 存储NULL值标记

数据区域 (data_width): 存储实际列数据

聚合状态区域 (aggr_width): 存储聚合函数状态

排序键区域 (sort_width): 存储排序相关数据

2. 主要特性

类型管理
1
vector<LogicalType> types;  // 列类型
2
Aggregates aggregates;      // 聚合函数
支持多种数据类型的列

管理聚合函数对象

提供类型安全的访问接口

嵌套结构支持
1
unique_ptr<unordered_map<idx_t, TupleDataLayout>> struct_layouts;
支持结构体类型的递归布局

每个结构体列都有自己的 TupleDataLayout

内存优化
1
bool all_constant;              // 是否所有列都是定长
2
vector<idx_t> variable_columns; // 变长列索引
3
idx_t heap_size_offset;         // 堆大小偏移
区分定长和变长列以优化内存使用

支持堆内存管理用于变长数据

初始化方法

1. 完整初始化
1
void Initialize(vector<LogicalType> types_p, Aggregates aggregates_p,
2
                TupleDataValidityType validity_type,
3
                TupleDataNestednessType nestedness_type);
2. 仅类型初始化
1
void Initialize(vector<LogicalType> types, TupleDataValidityType validity_type,
2
                TupleDataNestednessType nestedness_type);
3. 仅聚合初始化
1
void Initialize(Aggregates aggregates_p);
4. 排序布局初始化
1
void Initialize(const vector<BoundOrderByNode> &orders, const LogicalType &type,
2
                bool has_payload);
访问器方法

基本信息获取

ColumnCount(): 返回列数量

AggregateCount(): 返回聚合函数数量

GetTypes(): 获取列类型列表

GetAggregates(): 获取聚合函数列表

布局信息

GetRowWidth(): 整行宽度（包含填充）

GetDataOffset(): 数据区域起始偏移

GetDataWidth(): 数据区域宽度

GetAggrOffset(): 聚合区域起始偏移

GetAggrWidth(): 聚合区域宽度

GetOffsets(): 各列在行中的偏移

特殊属性检查

AllConstant(): 检查是否所有列都是定长

AllValid(): 检查是否所有列都不含NULL值

HasDestructor(): 检查聚合函数是否有析构器

IsSortKeyLayout(): 检查是否为排序键布局

排序支持
1
SortKeyType sort_key_type;
2
idx_t sort_width;
3
vector<idx_t> sort_skippable_bytes;
支持不同类型的排序键

提供排序优化，包括可跳过的字节

GetSortWidth() 和 GetSortSkippableBytes() 用于排序性能优化

内存管理特性

有效性管理
1
TupleDataValidityType validity_type;
支持不同的NULL值处理策略：

完全不允许NULL值

支持NULL值标记

资源清理
1
vector<idx_t> aggr_destructor_idxs;
跟踪需要析构的聚合函数索引

确保资源正确释放

使用场景

查询执行: 在各种算子中管理行数据布局

聚合操作: 存储和管理聚合函数状态

排序操作: 优化排序键的内存布局

数据交换: 在不同算子间传递结构化数据

内存优化: 最小化内存占用和缓存未命中

TupleDataLayout 是 DuckDB 高性能查询执行的关键组件，通过精确控制数据在内存中的布局来提升查询性能。

结语

对于Q1而言，DuckDB使用的Sort的本质用的还是插入排序InsertationSort

其速度提升主要来源于流程的优化——正如PR里所说的从ROwDataCollection转为了使用延迟指针（lazy pointer）TupleDataCollection，减轻数据溢出，降低合并成本