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_alignment2 的幂。每一行起始地址对齐到该字节数string_alignment2 的幂且不大于row_alignment。每个非 2 的幂长度的二进制字段以及每个变长字段的字节起始地址对齐到该字节数null_masks_bytes_per_row每一行用于编码空值掩码的固定字节数fixed_length固定长度行每行字节数向上取整到对齐倍数变长行所有编码后的固定长度键列的大小含变长列长度字段向上取整到 string 对齐varbinary_end_array_offset行内 32 位变长字段结束偏移数组的位置仅变长行使用offset_type固定为int64_t用于变长行的行偏移对齐的具体规则为每一行对齐到row_alignment字节长度非 2 的幂的固定长度列对齐到row_alignment字节变长列对齐到string_alignment字节。源码中通过padding_for_alignment_within_row()与padding_for_alignment_row()两个内联函数实现对齐计算基于(-offset) (alignment - 1)的位运算要求对齐值必须是 2 的幂。Buffer Layout行表的三个缓冲区与大多数 ArrowArray类似行表由最多三个缓冲区组成Null Masks Buffer空值掩码缓冲区指示每一行中每一列是否为空值Fixed-length Buffer固定长度缓冲区固定长度行表直接存储行数据变长行表存储指向变长数据的偏移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表示该列的值为 null0表示该列的值有效。注意这与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], ...]的行表在固定长度缓冲区中的存储如下Row 0Row 1Row 2...7 0 0 0, 0 (padding)8 0 0 0, 1 (padding)9 0 0 0, 0 (padding)...每一行先存放 4 字节的 int32小端序再存放 1 字节的 boolean最后是用于对齐的 padding。变长行的偏移在变长行表中固定长度缓冲区存放的是行偏移offsets指向存储在可选变长缓冲区中的行数据。偏移的类型为RowTableMetadata::offset_type固定为int64_t表示每行数据在变长缓冲区中的起始位置。变长行数据在变长行表中变长缓冲区包含连续存放的实际行数据固定长度缓冲区中的偏移指向每行数据的起始位置。RowTableImpl提供offsets()/var_length_rows()等访问器并在AppendEmpty/AppendSelectionFrom中按需扩容。Row Encoding变长行的行内编码变长行的编码顺序如下见文档与FromColumnMetadataVector的实现逻辑固定长度列先存储随后是指向各变长列的 32 位偏移序列每个偏移表示对应变长列在行数据内的结束位置end position变长列最后存储。例如schema 为(int32, string, string, int32)、数据为[[7, Alice, x, 0], [8, Bob, y, 1], [9, Charlotte, z, 2], ...]的行表假设变长列按 8 字节对齐存储如下固定长度缓冲区行偏移Row 0Row 1Row 2Row 3...0 0 0 0 0 0 0 032 0 0 0 0 0 0 064 0 0 0 0 0 0 0104 0 0 0 0 0 0 0...变长缓冲区行数据RowFixed-length ColsVarying-length OffsetsVarying-length Cols07 0 0 0, 0 0 0 021 0 0 0, 25 0 0 0Alice~~~x~~~~~~~18 0 0 0, 1 0 0 019 0 0 0, 25 0 0 0Bob~~~~~y~~~~~~~29 0 0 0, 2 0 0 025 0 0 0, 33 0 0 0Charlotte~~~~~~~z~~~~~~~3.........以 Row 0 为例固定长度部分为两个 int327与0变长偏移21与25分别表示 Alice 的结束位置A 在偏移 8 处Alice 结束于 81321与 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规则如下boolean 列以固定长度 0 标记视为固定长度部分为 1 字节固定长度部分为2 的幂或行对齐倍数的列排在其他列之前且按固定长度部分的大小降序排列固定长度部分大小相同的列固定长度列优先于变长列。这样排序的目的是让行内各列的访问对齐友好alignment-friendly。变长列的固定长度部分是其 32 位累计长度字段。排序结果记录在column_order与inverse_column_order中各列在行内的偏移记录在column_offsets中。类型到 KeyColumnMetadata 的映射列元数据由ColumnMetadataFromDataType()生成light_array_internal.cc它把 Arrow 数据类型映射为KeyColumnMetadata字典类型DICTIONARY视为固定长度宽度为 bit_width / 8BOOLfixed_length 0表示每值 1 位的位向量语义行表中展开为 1 字节固定宽度类型int/float/decimal 等fixed_length bit_width / 8binary-likebinary/string 等变长列offset 宽度sizeof(uint32_t)large binary-like变长列offset 宽度sizeof(uint64_t)NAnull类型固定长度、is_null_type true其余类型返回Status::TypeError即不支持作为行表键列。KeyColumnMetadata本身定义于 light_array_internal.h是arrow::DataType的零分配zero-allocation等价物仅描述列的固定/变长属性与每项字节数。编码流程EncodeSelected 的关键步骤将列式数据编码进行表由RowTableEncoder::EncodeSelected()完成encode_internal.cc其流程为rows-Clean()清空行表第一次AppendEmpty(num_selected, 0)扩充固定长度缓冲区含偏移缓冲区EncoderOffsets::GetRowOffsetsSelected()预先计算各变长行的长度填充偏移作为变长缓冲区扩容的目标大小第二次AppendEmpty(0, 0)依据已填充的偏移扩充变长缓冲区EncoderBinary::EncodeSelected()编码所有固定长度列按column_offsets定位行内偏移EncoderOffsets::EncodeSelected()写入变长列的行内 32 位结束偏移EncoderVarBinary::EncodeSelected()写入变长列的实际字节数据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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考