企业官网建设流程全解析

Apache Arrow C++ Compute 行表（Row Table）开发指南：Row-major 存储、编码格式与源码实现

【免费下载链接】arrowApache Arrow is the universal columnar format and multi-language toolbox for fast data interchange and in-memory analytics项目地址: https://gitcode.com/GitHub_Trending/arrow3/arrow

本篇指南面向 Apache Arrow C++ Compute 模块的开发者，系统讲解行表（Row Table）这一以行优先（row-major）方式组织数据的内存结构。行表是哈希表键、分组（grouping）与哈希连接（hash join）等算子的核心数据载体，阅读本文后，你将掌握RowTableMetadata的元数据与对齐规则、三缓冲区布局、变长行的编码格式（Row Encoding），并可从源码层面理解列排序、类型映射与编码流程的底层实现。

Row Table 是什么：为何需要行优先存储

在 Arrow 中，绝大多数数据以列式（column-major）的Array形式存储，这也是 Arrow 列式格式的核心优势。但Compute模块中的某些场景天然更适合行优先组织：例如对单行进行随机访问，且访问某一行时往往需要同时读取该行的所有列——最典型的就是哈希表键。

在 row_internal.h 中，RowTableImpl的注释给出了清晰的定位：

A table of data stored in row-major order. Can only store non-nested data types.

当数据以行形式连续存放时，哈希计算、键比较、分组与连接等操作能够借助连续内存访问改善缓存局部性（data locality），这正是 Row Table 相对列式存储的优势所在。从源码结构看，Row Table 被 grouper.cc（分组聚合）、swiss_join.cc（哈希连接）与 compare_internal.h（行比较/排序）等模块广泛使用。

RowTableMetadata：行表的元数据定义

一个行表由其元数据RowTableMetadata描述，它编码了 schema（列的类型与顺序）、对齐方式以及由此派生的属性。每一行按逻辑顺序依次存放各列数据（物理顺序可能不同，详见下文"行编码"一节）。

需要特别注意的是，文档明确指出：

嵌套类型（nested types）与大二进制类型（large binary types）的列不支持存储在行表中。

固定长度与变长行表

由 schema 派生的一个关键属性是行表是固定长度（fixed-length）还是变长（varying-length）：

• 固定长度行表：只包含固定长度列；
• 变长行表：至少包含一个变长列。

这一区分决定了行表的数据存储与访问方式。在源码中，该属性由RowTableMetadata::is_fixed_length字段表示，并在FromColumnMetadataVector()（见 row_internal.cc）中根据变长列的数量（num_varbinary_cols == 0）计算得出。

对齐规则

对齐是理解行布局的关键。RowTableMetadata定义了两种对齐参数（见 row_internal.h）：

对齐的具体规则为：

• 每一行对齐到row_alignment字节；
• 长度非 2 的幂的固定长度列对齐到row_alignment字节；
• 变长列对齐到string_alignment字节。

源码中通过padding_for_alignment_within_row()与padding_for_alignment_row()两个内联函数实现对齐计算（基于(-offset) & (alignment - 1)的位运算，要求对齐值必须是 2 的幂）。

Buffer Layout：行表的三个缓冲区

与大多数 ArrowArray类似，行表由最多三个缓冲区组成：

1. Null Masks Buffer（空值掩码缓冲区）：指示每一行中每一列是否为空值；
2. Fixed-length Buffer（固定长度缓冲区）：固定长度行表直接存储行数据；变长行表存储指向变长数据的偏移；
3. Varying-length Buffer（变长缓冲区，可选）：存储变长行的实际行数据；固定长度行表不使用。

在RowTableImpl中（row_internal.h），三个缓冲区分别由null_masks_、offsets_与rows_三个ResizableBuffer管理，UpdateBufferPointers()根据is_fixed_length决定buffers_数组的映射关系：

• 固定长度：buffers_[0] = null_masks_，buffers_[1] = rows_，buffers_[2] = nullptr；
• 变长：buffers_[0] = null_masks_，buffers_[1] = offsets_，buffers_[2] = rows_。

此外，每个缓冲区末尾都预留了kPaddingForVectors = 64字节的填充，以便向量化操作可以按块处理数据而无需担心尾部越界（见size_null_masks、size_offsets等函数）。缓冲区只增不减（"Buffers can only expand during lifetime and never shrink"），扩容时按 2 倍策略增长。

Row Format：行数据的存储细节

Null Masks：与 Array 有效性位图相反

对于每一行，一段连续的位序列表示该行各列是否为空。每一位对应一列：

• 1表示该列的值为 null；
• 0表示该列的值有效。

注意这与Array的 validity bitmap 约定相反（后者 1 表示有效）。每一行的空值掩码占用null_masks_bytes_per_row字节。源码中，null_masks_bytes_per_row被取为 2 的幂（从 1 字节开始，直到字节数 * 8 >= 列数），尽管文档注释说明这不是硬性要求，最小字节数即可满足需求（见 row_internal.cc 的FromColumnMetadataVector）。is_null()通过bit_util::GetBit读取对应位。

固定长度行数据

在固定长度行表中，行数据直接存储在固定长度缓冲区中，每行的所有列按序连续存放。一个特殊之处是boolean 列：在普通 ArrowArray中 boolean 使用 1 位存储，而在行表中占用1 字节。此时不使用变长缓冲区。

例如，schema 为(int32, boolean)、数据为[[7, false], [8, true], [9, false], ...]的行表，在固定长度缓冲区中的存储如下：

每一行先存放 4 字节的 int32（小端序），再存放 1 字节的 boolean，最后是用于对齐的 padding。

变长行的偏移

在变长行表中，固定长度缓冲区存放的是行偏移（offsets），指向存储在可选变长缓冲区中的行数据。偏移的类型为RowTableMetadata::offset_type，固定为int64_t，表示每行数据在变长缓冲区中的起始位置。

变长行数据

在变长行表中，变长缓冲区包含连续存放的实际行数据，固定长度缓冲区中的偏移指向每行数据的起始位置。RowTableImpl提供offsets()/var_length_rows()等访问器，并在AppendEmpty/AppendSelectionFrom中按需扩容。

Row Encoding：变长行的行内编码

变长行的编码顺序如下（见文档与FromColumnMetadataVector的实现逻辑）：

1. 固定长度列先存储；
2. 随后是指向各变长列的 32 位偏移序列，每个偏移表示对应变长列在行数据内的结束位置（end position）；
3. 变长列最后存储。

例如，schema 为(int32, string, string, int32)、数据为[[7, 'Alice', 'x', 0], [8, 'Bob', 'y', 1], [9, 'Charlotte', 'z', 2], ...]的行表（假设变长列按 8 字节对齐）存储如下：

固定长度缓冲区（行偏移）：

变长缓冲区（行数据）：

以 Row 0 为例：固定长度部分为两个 int32（7与0）；变长偏移21与25分别表示 'Alice' 的结束位置（'A' 在偏移 8 处，'Alice' 结束于 8+13=21）与 'x' 的结束位置（'x' 在 24 处，结束于 25）；~为对齐 padding。行偏移0、32、64、104依次指向各行数据在变长缓冲区中的起点。

源码中，RowTableMetadata::varbinary_end_array()返回行内变长字段结束偏移数组，first_varbinary_offset_and_length()与nth_varbinary_offset_and_length()则依据这些 32 位结束偏移和string_alignment计算每个变长字段的偏移与长度——后一个字段的起点需要将前一个字段的结束位置按对齐规则向上取整（见 row_internal.h）。

源码深潜：列排序、类型映射与编码流程

列编码顺序的排序规则

行内物理列顺序与逻辑 schema 顺序可能不同。FromColumnMetadataVector()会对列进行排序（row_internal.cc），规则如下：

1. boolean 列（以固定长度 0 标记）视为固定长度部分为 1 字节；
2. 固定长度部分为2 的幂或行对齐倍数的列排在其他列之前，且按固定长度部分的大小降序排列；
3. 固定长度部分大小相同的列，固定长度列优先于变长列。

这样排序的目的是让行内各列的访问对齐友好（alignment-friendly）。变长列的"固定长度部分"是其 32 位累计长度字段。排序结果记录在column_order与inverse_column_order中，各列在行内的偏移记录在column_offsets中。

类型到 KeyColumnMetadata 的映射

列元数据由ColumnMetadataFromDataType()生成（light_array_internal.cc），它把 Arrow 数据类型映射为KeyColumnMetadata：

• 字典类型（DICTIONARY）：视为固定长度，宽度为 bit_width / 8；
• BOOL：fixed_length = 0（表示每值 1 位的位向量语义，行表中展开为 1 字节）；
• 固定宽度类型（int/float/decimal 等）：fixed_length = bit_width / 8；
• binary-like（binary/string 等）：变长列，offset 宽度sizeof(uint32_t)；
• large binary-like：变长列，offset 宽度sizeof(uint64_t)；
• NA（null）类型：固定长度、is_null_type = true；
• 其余类型返回Status::TypeError，即不支持作为行表键列。

KeyColumnMetadata本身定义于 light_array_internal.h，是arrow::DataType的零分配（zero-allocation）等价物，仅描述列的固定/变长属性与每项字节数。

编码流程：EncodeSelected 的关键步骤

将列式数据编码进行表由RowTableEncoder::EncodeSelected()完成（encode_internal.cc），其流程为：

1. rows->Clean()清空行表；
2. 第一次AppendEmpty(num_selected, 0)：扩充固定长度缓冲区（含偏移缓冲区）；
3. EncoderOffsets::GetRowOffsetsSelected()：预先计算各变长行的长度，填充偏移，作为变长缓冲区扩容的目标大小；
4. 第二次AppendEmpty(0, 0)：依据已填充的偏移扩充变长缓冲区；
5. EncoderBinary::EncodeSelected()：编码所有固定长度列（按column_offsets定位行内偏移）；
6. EncoderOffsets::EncodeSelected()：写入变长列的行内 32 位结束偏移；
7. EncoderVarBinary::EncodeSelected()：写入变长列的实际字节数据；
8. EncoderNulls::EncodeSelected()：写入空值掩码。

这种"先扩固定缓冲区 → 计算偏移 → 再扩变长缓冲区 → 分类型写入"的两阶段扩容策略，保证了单次编码即可精确分配所需内存。解码则分为DecodeFixedLengthBuffers()与DecodeVaryingLengthBuffers()两步，前者先处理除变长缓冲区外的所有内容，输出可用于推算变长缓冲区大小，再调用后者完成解码。

内存消耗与测试验证

row_test.cc 中的RowTableMemoryConsumption.Encode测试对多种固定长度列（int8、uint16、int32、uint64、fixed_size_binary(16/32)）与变长列进行编码，断言各缓冲区大小满足实际大小 <= buffer_size - 64（向量填充）< 实际大小 * 2，验证了缓冲区按 2 倍容量增长的策略；RowTableLarge测试（GH-43495）则确保行表能够承载超过 4GB 的行数据。这些测试同时印证了三种缓冲区的存在：固定长度表使用null_masks与fixed_length_rows缓冲区，变长表额外使用offsets与var_length_rows缓冲区。

应用场景：Row Table 在 Compute 中的角色

从源码调用关系可以确认，Row Table 是多个核心算子的基础设施：

• 分组聚合：grouper.cc 中GrouperFastImpl持有RowTableImpl rows_、RowTableImpl rows_minibatch_与RowTableEncoder encoder_，将输入批次编码为行键后借助哈希表完成分组；
• 哈希连接：swiss_join.cc（以及 AVX2 变体 swiss_join_avx2.cc）利用行表构造连接键进行探测与匹配；
• 行比较/排序：compare_internal.h（含 AVX2 实现）基于行表编码做键比较，服务于排序索引、去重等操作。

此外，row/目录下还存在encode_internal_avx2.cc、row_util_avx2_internal.h等 SIMD 加速实现，表明行表的热路径（编码与比较）针对现代 CPU 做了向量化优化——这正体现了文档所述"优化内存访问模式与数据局部性"的设计初衷。

总结

Row Table 是 Arrow C++ Compute 中连接列式存储与行式处理的关键桥梁：它以RowTableMetadata精确描述行布局与对齐约束，用三个缓冲区分别承载空值掩码、固定长度数据（或行偏移）与变长数据，并通过一套精心设计的编码顺序（固定列在前、32 位结束偏移居中、变长列在后）保证随机访问与缓存局部性。理解其元数据、缓冲区布局与编码格式，是深入阅读分组、连接、排序等算子源码，乃至为 Compute 模块贡献新功能的基础。

进一步阅读：

• 本文对应官方开发者文档：docs/source/developers/cpp/compute.rst
• 行表核心实现：cpp/src/arrow/compute/row/row_internal.h、cpp/src/arrow/compute/row/row_internal.cc
• 编码器实现：cpp/src/arrow/compute/row/encode_internal.h、cpp/src/arrow/compute/row/encode_internal.cc
• 键列元数据与类型映射：cpp/src/arrow/compute/light_array_internal.h、cpp/src/arrow/compute/light_array_internal.cc
• 测试用例：cpp/src/arrow/compute/row/row_test.cc

【免费下载链接】arrowApache Arrow is the universal columnar format and multi-language toolbox for fast data interchange and in-memory analytics项目地址: https://gitcode.com/GitHub_Trending/arrow3/arrow