The columnar format has some key features:
- Data adjacency for sequential access (scans)
- O(1) (constant-time) random access
- SIMD and vectorization-friendly
- Relocatable without “pointer swizzling”, allowing for true zero-copy access in shared memory
仅针对 in-memory 的数据表示和序列化，其他如：协调数据变更，则由具体应用来实现。
physical layout vs logical type
不同的 logical type 如 decimal、time 等可能使用相同的 physical layout。主要的物理 layout 包括：
- Null: a sequence of all null values, having null logical type
大量场景是基于 array 进行操作，所以 memory layout 的设计主要集中于 array。
null count
array 中的 null 值数量
Arrays 的 physical memory layout
包括 metadata 和 data
- A logical data type.
- A sequence of buffers.
- A length as a 64-bit signed integer. Implementations are permitted to be limited to 32-bit lengths, see more on this below.
- A null count as a 64-bit signed integer.
- An optional dictionary, for dictionary-encoded arrays.
buffer 对齐和补齐
If possible, we suggest that you prefer using 64-byte alignment and padding.
validity bitmaps
在大量 null 值存在的场景更加适用。当 null count 为 0 时，可以不分配 validity bitmap。
Fixed-size 定长 layout
variable-size 变长 layout
offset buffer 和 data buffer
offset buffer 相邻的两个 integer（32位或64位） slot postion = offset[j] length = offset[j+1] - offset[j]
变长 list layout
定长 list layout
定长 list 是一种嵌入式类型，每个 array slot 包含固定长度的相同类型的 value 序列。
定长 list 中 slot j 的 value 保存于一个整个 values array 中长度为 N 的 slice 中，起始位置为 j * N 。
疑问： https://arrow.apache.org/docs/format/Columnar.html#fixed-size-list-layout 中的 null 值为何不在 values array 进行压缩？
struct layout
清晰的表现出了 columnar storage 的布局特点。每一类 field 的 memory 是连续的。各类 filed 则是间隔存储。
Dictionary-encoded Layout
推荐使用有符号 integer 作为字典索引，因为无符号 integer 在一些情况下存在问题（JVM 不支持 unsigned） 避免使用 64 位 unsigned int 作为字典索引。
各种类型的 layout 对 buffer 的需求
这里都针对 Array
| LayoutType | Buffer 0 | Buffer 1 | Buffer 2 |
|---|---|---|---|
| Primitive | validity | data | |
| Variable Binary | validity | offsets | data |
| List | validity | offsets | |
| Fixed-size List | validity | ||
| Struct | validity | ||
| Sparse Union | type ids | ||
| Dense Union | type ids | offsets | |
| Null | |||
| Dictionary-encoded | validity | data (indices) |
这里的字典编码的内容似乎不对，并没有 validity 的内容。
序列化与 IPC
record batch 的概念是序列化的最小单位。是arrays 的一组 ordered 集合。 类似于 parquet 格式中的 row group 。
设计目的是：将 record batch 序列化为二进制 payload 的流用于传输，并且在从 playload 重建 record batch 时无需 memory copy。
IPC 协议是一个单向的二进制消息包括：
- Schema
- RecordBatch
- DictionaryBatch
使用 flatbuffer 以及 optional 的 message body 。
Encapsulated message format
在序列化时仅检查消息的 metadata ，无需对实际的数据进行 copy 或 move。
压缩的二进制消息格式如下：
- 32-bit continuation indicator，标识器，0xFFFFFFFF 表示有效的消息。
- 32-bit little-endian length，表示 metadata 大小。包含 metadata_flatbuffer + padding 的大小。
- metadata 数据 ， 在 Message.fbs 中的 Message 定义。包含 MessageHader, bodyLength, custom_metadata
- 8-byte 对齐 metadata_flatbuffer 的 padding 数据
- 消息体数据，长度必须为 8 bytes 的倍数
MessageHeader 是 Schema, RecordBatch, DictionaryBatch, Tensor, SparseTensor 的一种。
Schema message
序列化的 Schema 不包含 data ，仅有 type metadata 。包含 ordered sequence of field， 每个 field 包含 name 和 type。
RecordBatch message
对应真正的数据 buffer 的物理内存 layout 。metadata 提供了每个 buffer 的 location 和 size ，从而使得数据的重建通过指针运算而无需内存 copy 。
序列化的 record batch 格式如下：
- data header ， 主要是 filedNode，包含 field 的 length 和 null count 。
- body
基于打平的结构，通过 pre-order depth-first 的遍历。
buffer 对应 filed node 的打平顺序。
ByteOrder
默认是 little endian
IPC streaming format
dictionary 可以分段，使用 isDelta 字段来控制。