Arrow 列式格式

Arrow 列式格式#

“Arrow 列式格式”包括一种与语言无关的内存数据结构规范、元数据序列化以及用于序列化和通用数据传输的协议。

本文档旨在提供足够的细节，以便在没有现有实现的帮助下创建列式格式的新实现。我们利用 Google 的 Flatbuffers 项目进行元数据序列化，因此在阅读本文档时，有必要参考该项目的 Flatbuffers 协议定义文件。

列式格式具有一些关键特性：

  • 顺序访问（扫描）时的数据邻近性

  • O(1)（常数时间）的随机访问

  • 适合 SIMD 和向量化

  • 无需“指针混洗”(“pointer swizzling”)即可重新定位，允许在共享内存中实现真正的零拷贝访问(zero-copy access)

Arrow 列式格式提供了分析性能和数据局部性保证，以换取相对更昂贵的变更操作。本文档仅关注内存数据表示和序列化细节；诸如协调数据结构的变更等问题留给实现来处理。

术语#

由于不同的项目使用了不同的词汇来描述各种概念，这里有一个小型词汇表帮助消除歧义。

  • 数组(Array)或向量(Vector)：一系列具有已知长度且类型相同的值。这些术语在不同的 Arrow 实现中可互换使用，但在本文中我们使用“数组”。

  • 插槽(Slot)：数组中某个特定数据类型的单个逻辑值。

  • 缓冲区(Buffer)或连续内存区域(Contiguous memory region)：一个给定长度的连续虚拟地址空间。任何字节都可以通过小于该区域长度的单个指针偏移来访问。

  • 物理布局(Physical Layout)：数组的底层内存布局，不考虑任何值的语义。例如，32 位有符号整数数组和32位浮点数数组具有相同的布局。

  • 父数组和子数组：用于表达嵌套类型结构中物理值数组之间关系的名称。例如，List<T> 类型的父数组有 T 类型的数组作为其子数组（关于列表的更多信息请参见下文）。

  • 原始类型(Primitive type)：没有子类型的数据类型。这包括固定位宽、可变大小的二进制和空值类型。

  • 嵌套类型：其完整结构依赖于一个或多个其他子类型的数据类型。如果两个完全指定的嵌套类型的子类型相等，则这两个嵌套类型相等。例如，List<U> 与 List<V> 不同，当且仅当 U 和 V 是不同的类型。

  • 逻辑类型：面向应用程序的语义值类型，它使用某种物理布局来实现。例如，Decimal 值以 16 字节的固定大小二进制布局存储。同样，字符串可以存储为 List<1-byte>。时间戳(timestamp)可能存储为 64 位固定大小布局。

物理内存布局#

数组由以下几部分组成：

  • 逻辑数据类型。

  • 一系列缓冲区。

  • 64 位有符号整数表示的长度。实现可以限制为 32 位长度，具体请参阅下文。

  • 64 位有符号整数表示的空值计数。

  • 可选的字典，用于字典编码的数组。

嵌套数组还包括一个或多个这些项目的序列，称为子数组。

每个逻辑数据类型都有一个明确的物理布局。以下是 Arrow 定义的不同物理布局：

  • Primitive (fixed-size)：一系列具有相同字节或位宽的值。

  • Variable-size Binary：一系列每个值都具有可变的字节长度。支持两种变体，使用32位和64位长度编码。

  • View of Variable-size Binary：一系列每个值都具有可变的字节长度。与可变大小二进制相对比，这种布局的值分布潜在地跨越多个缓冲区，而不是在单个缓冲区中密集且顺序排列。

  • Fixed-size List：一种嵌套布局，其中每个值都有来自子数据类型的相同数量的元素。

  • Variable-size List：一种嵌套布局，其中每个值都是来自子数据类型的可变长度值序列。支持两种变体，使用32位和64位长度编码。

  • View of Variable-size List：一种嵌套布局，其中每个值都是来自子数据类型的可变长度值序列。这种布局与可变大小列表不同之处在于它有一个额外的缓冲区包含每个列表值的大小。这消除了对偏移量缓冲区的约束——它不需要有序。

  • Struct：一种由一系列命名的子字段组成的嵌套布局，每个字段有相同的长度但可能有不同的类型。

  • Sparse and Dense Union：一种表示一系列值的嵌套布局，其中每个值都可以从子数组类型的集合中选择类型。

  • Dictionary-Encoded：一种布局，由一系列整数（任意位宽）组成，这些整数代表一个可以是任何类型的字典中的索引。

  • Run-End Encoded (REE)：一种由两个子数组组成的嵌套布局，一个代表值，另一个代表相应值的运行结束的逻辑索引。

  • Null：一系列全为空值的序列，具有空逻辑类型。

Arrow 列式内存布局仅适用于数据，而不适用于元数据。实现可以自由地以任何方便的形式在内存中表示元数据。我们使用 Flatbuffers 以一种与实现无关的方式来处理元数据序列化，详见下文。

缓冲区对齐和填充#

建议实现在对齐地址（8 字节或 64 字节的倍数）上分配内存，并对长度进行 pad（overallocate），使其成为 8 或 64 字节的倍数。在为进程间通信序列化 Arrow 数据时，这些对齐和填充要求将被强制执行。如果可能，我们建议您优先使用 64 字节的对齐和填充。除非另有说明，填充字节不需要具有特定值。

对齐要求遵循优化内存访问的最佳实践：

  • 数值数组中的元素将保证通过对齐访问来检索。

  • 在某些架构上，对齐可以帮助限制部分使用的缓存行。

推荐 64 字节对齐的建议来自于英特尔性能指南，该指南建议将内存对齐以匹配 SIMD 寄存器的宽度。选择特定的填充长度是因为它与广泛部署的 x86 架构上可用的最大 SIMD 指令寄存器（Intel AVX-512）相匹配。

推荐使用 64 字节的填充可以允许在循环中一致地使用 SIMD 指令，而无需额外的条件检查。这应该允许编写更简单、高效且对 CPU 缓存友好的代码。换句话说，我们可以将整个 64 字节的缓冲区加载到一个 512 位宽的 SIMD 寄存器中，并在所有打包到 64 字节缓冲区的列值上获得数据级并行性。保证的填充也可以让某些编译器直接生成更优化的代码（例如，可以安全地使用 Intel 的 -qopt-assume-safe-padding）。

数组长度#

数组长度在 Arrow 元数据中表示为64位有符号整数。即使只支持最大32位有符号整数的长度，Arrow的实现也被认为是有效的。如果在多语言环境中使用Arrow，我们建议将长度限制在\(2^{31}-1\)个元素或更少。更大的数据集可以使用多个数组块来表示。

空值计数#

空值槽的数量是物理数组的一个属性，并且被认为是数据结构的一部分。空值计数(null count)在 Arrow 元数据中表示为 64 位有符号整数，因为它可能与数组长度一样大。

有效性位图#

备注

有效性位图（Validity Bitmaps）是用于表示数据结构中元素是否为有效的一种机制，在处理包含空值的数据时尤其有用。在Apache Arrow等高效的数据列式存储格式中，为了优化性能和减少存储空间，常常会用到有效性位图。

以下是对有效性位图的解读：

  1. 目的：有效性位图的主要目的是标记数组中的每个元素是否为空（null）。这对于数据分析和查询非常重要，因为在进行操作之前需要知道哪些数据是有效的，哪些是无效的（即空值）。

  2. 实现：在大多数实现中，有效性位图是一个二进制数组，其中每个位（bit）对应于数据数组中的一个元素。如果某一位被设置为1，那么对应的元素是有效的（非空）；如果被设置为0，则表示对应的元素是空值。

  3. 内存效率：使用位图而不是整数值来标记空值可以极大地节省内存。例如，对于一个有10亿个元素的数组，如果使用整数来标记每个元素是否为空，可能需要额外的数十亿字节的内存。而使用位图，只需要几百兆字节。

  4. 初始化：位图在创建时应全部初始化为0，这表示所有元素最初都被认为是空的。随着数据的填充，位图会被更新以反映实际的空值情况。

  5. 性能优化：通过使用有效性位图，数据处理系统可以快速地识别出所有的空值，而不需要遍历整个数组。这有助于提高查询和分析的性能，尤其是在处理大型数据集时。

  6. 填充位：即使在数组未满时，位图也应该包含足够的位来表示所有的数组槽位，包括可能的填充位（padding）。这意味着位图的大小与数组的最大容量相匹配，而不是当前存储的元素数量。

  7. 多语言兼容性：有效性位图提供了一种跨语言和平台的标准化方法来处理空值，这有助于在不同的编程语言和工具之间实现数据的互操作性。

总之，有效性位图是一种高效、节省空间的方法，用于在数据结构中跟踪和处理空值。它是Apache Arrow等先进数据处理技术中不可或缺的一部分。

数组中的任何值在语义上都可能为空，无论是 primitive 类型还是嵌套类型。

除了联合类型（稍后会详细介绍）之外，所有数组类型都使用专门的内存缓冲区，称为有效（或“空值”）位图，来编码每个值槽的空值或非空值状态。有效性位图必须足够大，至少为每个数组槽提供1位。

数组槽是否有效（非空）在该位图的相应位中进行编码。对于索引 j，位图中的1（设置位）表示该值不为空，而0（未设置位）表示该值为空。位图在分配时应初始化为全未设置状态（包括填充）：

is_valid[j] -> bitmap[j / 8] & (1 << (j % 8))

我们使用最低有效位（least-significant bit，LSB）编号（也称为位序(bit-endianness)）。这意味着在一组 8 位中，我们从右向左读取：

values = [0, 1, null, 2, null, 3]

bitmap
j mod 8   7  6  5  4  3  2  1  0
          0  0  1  0  1  0  1  1

具有 0 空值计数的数组可以选择不分配有效性位图；这如何表示取决于实现（例如，C++ 实现可能使用 NULL 指针来表示这种“缺失”的有效性位图）。实现可能会出于方便而选择始终分配有效性位图。Arrow 数组的使用者应该准备好处理这两种可能性。

嵌套类型数组（除了上面提到的联合类型）拥有自己的顶级有效性位图和空值计数，不管它们的子数组的空值计数和有效位如何。

为空的数组槽不需要具有特定值；任何被“掩盖”的内存都可以具有任何值，不必为零，尽管实现经常选择将空值的内存置零。

固定大小的 Primitive 布局#

Primitive 值数组表示一个值数组，每个值具有相同的物理槽宽度，通常以字节为单位进行测量，尽管规范也提供了位压缩类型（例如，以位编码的布尔值）。

在内部，数组包含一个连续的内存缓冲区，其总大小至少与槽宽度乘以数组长度一样大。对于位压缩类型，大小会向上舍入到最接近的字节。

关联的有效性位图是连续分配的（如上所述），但不需要在内存中与值缓冲区相邻。

示例布局：Int32 数组#

例如，int32类型的 Primitive 数组：

[1, null, 2, 4, 8]

看起来是：

* Length: 5, Null count: 1
* Validity bitmap buffer:

  | Byte 0 (validity bitmap) | Bytes 1-63            |
  |--------------------------|-----------------------|
  | 00011101                 | 0 (padding)           |

* Value Buffer:

  | Bytes 0-3   | Bytes 4-7   | Bytes 8-11  | Bytes 12-15 | Bytes 16-19 | Bytes 20-63           |
  |-------------|-------------|-------------|-------------|-------------|-----------------------|
  | 1           | unspecified | 2           | 4           | 8           | unspecified (padding) |

示例布局：Non-null int32 数组#

[1, 2, 3, 4, 8] 有两种可能的布局：

* Length: 5, Null count: 0
* Validity bitmap buffer:

  | Byte 0 (validity bitmap) | Bytes 1-63            |
  |--------------------------|-----------------------|
  | 00011111                 | 0 (padding)           |

* Value Buffer:

  | Bytes 0-3   | Bytes 4-7   | Bytes 8-11  | Bytes 12-15 | Bytes 16-19 | Bytes 20-63           |
  |-------------|-------------|-------------|-------------|-------------|-----------------------|
  | 1           | 2           | 3           | 4           | 8           | unspecified (padding) |

或者省略位图：

* Length 5, Null count: 0
* Validity bitmap buffer: Not required
* Value Buffer:

  | Bytes 0-3   | Bytes 4-7   | Bytes 8-11  | bytes 12-15 | bytes 16-19 | Bytes 20-63           |
  |-------------|-------------|-------------|-------------|-------------|-----------------------|
  | 1           | 2           | 3           | 4           | 8           | unspecified (padding) |

变长二进制布局#

这种布局中的每个值由 0 个或多个字节组成。虽然原始数组只有一个值缓冲区，但变长二进制数组有一个偏移量缓冲区(offsets buffer)和数据缓冲区(data buffer)。

偏移量缓冲区包含 length+1 的有符号整数（根据逻辑类型，可以是 32 位或 64 位），它们编码了数据缓冲区中每个槽的起始位置。每个槽中的值的长度是通过该槽索引处的偏移量与后续偏移量之间的差异来计算的。例如，槽 j 的位置和长度计算为：

slot_position = offsets[j]
slot_length = offsets[j + 1] - offsets[j]  // (for 0 <= j < length)

应该注意的是，空值可能具有正的槽长度。也就是说，空值可能在数据缓冲区中占用非空的内存空间。当这是真的时，相应内存空间的内容是未定义的。

偏移量必须单调递增，即对于 0 <= j < length，offsets[j+1] >= offsets[j]，即使对于空槽也是如此。这一属性确保了所有值的位置都是有效且明确定义的。

通常，偏移量数组中的第一个槽是 0，最后一个槽是值数组的长度。在序列化这种布局时，我们建议将偏移量标准化为从 0 开始。

示例布局：VarBinary#

['joe', null, null, 'mark'] 将表示如下：

* Length: 4, Null count: 2
* Validity bitmap buffer:

  | Byte 0 (validity bitmap) | Bytes 1-63            |
  |--------------------------|-----------------------|
  | 00001001                 | 0 (padding)           |

* Offsets buffer:

  | Bytes 0-19     | Bytes 20-63           |
  |----------------|-----------------------|
  | 0, 3, 3, 3, 7  | unspecified (padding) |

 * Value buffer:

  | Bytes 0-6      | Bytes 7-63            |
  |----------------|-----------------------|
  | joemark        | unspecified (padding) |

变长二进制视图布局#

这种布局中的每个值由 0 个或多个字节组成。这些字节的位置使用视图缓冲区(views buffer)指示，该缓冲区可能指向潜在的几个数据缓冲区(data buffer)之一，或者可能内联包含字符。

视图缓冲区包含长度为 view 结构的数量，具有以下布局：

* Short strings, length <= 12
  | Bytes 0-3  | Bytes 4-15                            |
  |------------|---------------------------------------|
  | length     | data (padded with 0)                  |

* Long strings, length > 12
  | Bytes 0-3  | Bytes 4-7  | Bytes 8-11 | Bytes 12-15 |
  |------------|------------|------------|-------------|
  | length     | prefix     | buf. index | offset      |

无论是长字符串还是短字符串的情况，前四个字节都编码了字符串的长度，并可以用来确定如何解释视图的其余部分。

在短字符串的情况下，字符串的字节是内联的——存储在视图本身中，跟随长度之后的十二个字节中。

在长字符串的情况下，一个缓冲区索引指示哪个数据缓冲区存储了数据字节，并且一个偏移量指示在该缓冲区中数据字节开始的位置。缓冲区索引0指的是第一个数据缓冲区，即有效性缓冲区和视图缓冲区之后的第一个缓冲区。半开区间 [offset, offset + length) 必须完全包含在所指示的缓冲区内。字符串的前四个字节的副本以内联方式存储在长度之后的前缀中。这个前缀为字符串比较提供了有益的快速路径，这些比较通常在前四个字节内就能确定。

所有整数（长度、缓冲区索引和偏移量）都是有符号的。

这种布局是改编自慕尼黑工业大学的 UmbraDB。

变长列表布局#

列表是一种嵌套类型，在语义上与变长二进制相似。有两种列表布局变体——“list”和“list-view”——每种变体都可以由32位或64位偏移整数分隔。

列表布局#

列表布局由两个缓冲区定义，一个有效性位图和一个偏移量缓冲区，以及一个子数组。偏移量与变长二进制情况中的相同，支持32位和64位有符号整数偏移量作为偏移量的选项。这些偏移量不是引用额外的数据缓冲区，而是引用子数组。

与变长二进制的布局类似，空值可能对应于子数组中的一个非空段。当这是真的时，相应段的内容可以是任意的。

列表类型被指定为 List<T>，其中 T 是任何类型（原始或嵌套）。在这些示例中，我们使用32位偏移量，其中64位偏移量版本将由 LargeList<T> 表示。

示例布局：List<Int8> 数组#

我们展示了一个长度为4且具有以下值的 List<Int8> 的示例：

[[12, -7, 25], null, [0, -127, 127, 50], []]

将具有以下表示：

* Length: 4, Null count: 1
* Validity bitmap buffer:

  | Byte 0 (validity bitmap) | Bytes 1-63            |
  |--------------------------|-----------------------|
  | 00001101                 | 0 (padding)           |

* Offsets buffer (int32)

  | Bytes 0-3  | Bytes 4-7   | Bytes 8-11  | Bytes 12-15 | Bytes 16-19 | Bytes 20-63           |
  |------------|-------------|-------------|-------------|-------------|-----------------------|
  | 0          | 3           | 3           | 7           | 7           | unspecified (padding) |

* Values array (Int8Array):
  * Length: 7,  Null count: 0
  * Validity bitmap buffer: Not required
  * Values buffer (int8)

    | Bytes 0-6                    | Bytes 7-63            |
    |------------------------------|-----------------------|
    | 12, -7, 25, 0, -127, 127, 50 | unspecified (padding) |
示例布局：List<List<Int8>>#

[[[1, 2], [3, 4]], [[5, 6, 7], null, [8]], [[9, 10]]] 将表示如下：

* Length 3
* Nulls count: 0
* Validity bitmap buffer: Not required
* Offsets buffer (int32)

  | Bytes 0-3  | Bytes 4-7  | Bytes 8-11 | Bytes 12-15 | Bytes 16-63           |
  |------------|------------|------------|-------------|-----------------------|
  | 0          |  2         |  5         |  6          | unspecified (padding) |

* Values array (`List<Int8>`)
  * Length: 6, Null count: 1
  * Validity bitmap buffer:

    | Byte 0 (validity bitmap) | Bytes 1-63  |
    |--------------------------|-------------|
    | 00110111                 | 0 (padding) |

  * Offsets buffer (int32)

    | Bytes 0-27           | Bytes 28-63           |
    |----------------------|-----------------------|
    | 0, 2, 4, 7, 7, 8, 10 | unspecified (padding) |

  * Values array (Int8):
    * Length: 10, Null count: 0
    * Validity bitmap buffer: Not required

      | Bytes 0-9                     | Bytes 10-63           |
      |-------------------------------|-----------------------|
      | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 | unspecified (padding) |

ListView 布局#

ListView 布局由三个缓冲区定义：一个有效性位图、一个偏移量缓冲区和一个额外的大小缓冲区。大小和偏移量具有相同的位宽度，支持32位和64位有符号整数选项。

与 List 布局一样，偏移量编码子数组中每个槽的起始位置。与 List 布局不同的是，列表长度明确存储在大小缓冲区中，而不是推断得出。这允许偏移量无序排列。子数组的元素不必按照它们在父数组的列表元素中逻辑上出现的顺序存储。

每个 list-view 值，包括空值，都必须保证以下不变性：

0 <= offsets[i] <= length of the child array
0 <= offsets[i] + size[i] <= length of the child array

list-view 类型被指定为 ListView<T>，其中 T 是任何类型（原始或嵌套）。在这些示例中，我们使用32位偏移量和大小，其中64位版本将由 LargeListView<T> 表示。

示例布局：ListView<Int8> 数组#

我们展示了一个长度为4且具有以下值的 ListView<Int8> 的示例：

[[12, -7, 25], null, [0, -127, 127, 50], []]

表示如下：

* Length: 4, Null count: 1
* Validity bitmap buffer:

  | Byte 0 (validity bitmap) | Bytes 1-63            |
  |--------------------------|-----------------------|
  | 00001101                 | 0 (padding)           |

* Offsets buffer (int32)

  | Bytes 0-3  | Bytes 4-7   | Bytes 8-11  | Bytes 12-15 | Bytes 16-63           |
  |------------|-------------|-------------|-------------|-----------------------|
  | 0          | 7           | 3           | 0           | unspecified (padding) |

* Sizes buffer (int32)

  | Bytes 0-3  | Bytes 4-7   | Bytes 8-11  | Bytes 12-15 | Bytes 16-63           |
  |------------|-------------|-------------|-------------|-----------------------|
  | 3          | 0           | 4           | 0           | unspecified (padding) |

* Values array (Int8Array):
  * Length: 7,  Null count: 0
  * Validity bitmap buffer: Not required
  * Values buffer (int8)

    | Bytes 0-6                    | Bytes 7-63            |
    |------------------------------|-----------------------|
    | 12, -7, 25, 0, -127, 127, 50 | unspecified (padding) |
示例布局 ListView<Int8> Array#

我们继续使用 ListView<Int8> 类型，但这个实例展示了偏移量无序排列和子数组值的共享。它是一个长度为5的数组，具有逻辑值：

[[12, -7, 25], null, [0, -127, 127, 50], [], [50, 12]] 表示如下：

* Length: 4, Null count: 1
* Validity bitmap buffer:

  | Byte 0 (validity bitmap) | Bytes 1-63            |
  |--------------------------|-----------------------|
  | 00011101                 | 0 (padding)           |

* Offsets buffer (int32)

  | Bytes 0-3  | Bytes 4-7   | Bytes 8-11  | Bytes 12-15 | Bytes 16-19 | Bytes 20-63           |
  |------------|-------------|-------------|-------------|-------------|-----------------------|
  | 4          | 7           | 0           | 0           | 3           | unspecified (padding) |

* Sizes buffer (int32)

  | Bytes 0-3  | Bytes 4-7   | Bytes 8-11  | Bytes 12-15 | Bytes 16-19 | Bytes 20-63           |
  |------------|-------------|-------------|-------------|-------------|-----------------------|
  | 3          | 0           | 4           | 0           | 2           | unspecified (padding) |

* Values array (Int8Array):
  * Length: 7,  Null count: 0
  * Validity bitmap buffer: Not required
  * Values buffer (int8)

    | Bytes 0-6                    | Bytes 7-63            |
    |------------------------------|-----------------------|
    | 0, -127, 127, 50, 12, -7, 25 | unspecified (padding) |

固定大小列表布局#

固定大小列表是一种嵌套类型，其中每个数组槽位包含一系列固定大小的值，这些值都具有相同的类型。

固定大小列表类型被指定为 FixedSizeList<T>[N]，其中 T 是任何类型（原始或嵌套），N 是一个32位有符号整数，表示列表的长度。

固定大小列表数组由一个值数组表示，该数组是一个类型为 T 的子数组。T 也可以是一个嵌套类型。固定大小列表数组的槽位 j 中的值存储在值数组中，从偏移量 j * N 开始的 N 长的切片中。

示例布局：FixedSizeList<byte>[4] 数组

在这里我们展示了 FixedSizeList<byte>[4]。

对于一个长度为4且具有以下相应值的数组：

[[192, 168, 0, 12], null, [192, 168, 0, 25], [192, 168, 0, 1]]

表示为：

* Length: 4, Null count: 1
* Validity bitmap buffer:

  | Byte 0 (validity bitmap) | Bytes 1-63            |
  |--------------------------|-----------------------|
  | 00001101                 | 0 (padding)           |

* Values array (byte array):
  * Length: 16,  Null count: 0
  * validity bitmap buffer: Not required

    | Bytes 0-3       | Bytes 4-7   | Bytes 8-15                      |
    |-----------------|-------------|---------------------------------|
    | 192, 168, 0, 12 | unspecified | 192, 168, 0, 25, 192, 168, 0, 1 |

结构体布局#

结构体是一种嵌套类型，由一系列有序的类型参数化（这些类型可以完全不同），称为其字段。每个字段必须有一个 UTF8 编码的名称，这些字段名是类型元数据的一部分。

从物理上讲，一个结构体数组为每个字段有一个子数组。子数组是独立的，不必在内存中相邻。结构体数组还有一个有效性位图，用于编码顶层的有效性信息。

例如，结构体（出于说明目的，这里将字段名显示为字符串）：

Struct <
  name: VarBinary
  age: Int32
>

具有两个子数组，一个 VarBinary 数组（使用变长二进制布局）和一个具有 Int32 逻辑类型的 4 字节原始值数组。

示例布局：Struct<VarBinary, Int32>#

布局为 [{'joe', 1}, {null, 2}, null, {'mark', 4}]，具有子数组 ['joe', null, 'alice', 'mark'] 和 [1, 2, null, 4] 将是：

* Length: 4, Null count: 1
* Validity bitmap buffer:

  | Byte 0 (validity bitmap) | Bytes 1-63            |
  |--------------------------|-----------------------|
  | 00001011                 | 0 (padding)           |

* Children arrays:
  * field-0 array (`VarBinary`):
    * Length: 4, Null count: 1
    * Validity bitmap buffer:

      | Byte 0 (validity bitmap) | Bytes 1-63            |
      |--------------------------|-----------------------|
      | 00001101                 | 0 (padding)           |

    * Offsets buffer:

      | Bytes 0-19     | Bytes 20-63           |
      |----------------|-----------------------|
      | 0, 3, 3, 8, 12 | unspecified (padding) |

     * Value buffer:

      | Bytes 0-11     | Bytes 12-63           |
      |----------------|-----------------------|
      | joealicemark   | unspecified (padding) |

  * field-1 array (int32 array):
    * Length: 4, Null count: 1
    * Validity bitmap buffer:

      | Byte 0 (validity bitmap) | Bytes 1-63            |
      |--------------------------|-----------------------|
      | 00001011                 | 0 (padding)           |

    * Value Buffer:

      | Bytes 0-3   | Bytes 4-7   | Bytes 8-11  | Bytes 12-15 | Bytes 16-63           |
      |-------------|-------------|-------------|-------------|-----------------------|
      | 1           | 2           | unspecified | 4           | unspecified (padding) |

结构体有效性#

一个结构体数组拥有自己的有效性位图，这个位图独立于其子数组的有效性位图。结构体数组的有效性位图可能在其一个或多个子数组的相应槽位中有非空值时指示为空；或者相反，子数组可能在其有效性位图中指示为空，而结构体数组的有效性位图显示非空值。

因此，要知道特定的子项是否有效，必须取两个有效性位图（结构体数组的和子数组的）中相应位的逻辑与。

这在上面的例子中有所说明，其中一个子数组对于空结构体有一个有效的条目 'alice'，但它被结构体数组的有效性位图“隐藏”了。然而，当独立对待时，子数组的相应条目将是非空的。

联合布局#

联合由一系列有序的类型定义；联合中的每个槽位都可以有一个选自这些类型的值。这些类型就像结构体的字段一样命名，这些名称是类型元数据的一部分。

与其他数据类型不同，联合没有自己的有效性位图。相反，每个槽位的空值完全由组成联合的子数组决定。

我们定义了两种不同的联合类型，“密集型”(“dense”)和“稀疏型”(“sparse”)，它们针对不同的用例进行了优化。

密集联合#

密集联合(Dense union)表示一个混合类型数组，每个值有5字节的开销。它的物理布局如下：

  • 每种类型一个子数组

  • 类型缓冲区：一个8位有符号整数的缓冲区。联合中的每种类型都有一个对应的类型id，其值在这个缓冲区中可以找到。具有超过127种可能类型的联合可以被建模为联合的联合。

  • 偏移量缓冲区：一个有符号Int32值的缓冲区，指示给定槽位中类型的相对偏移量进入相应的子数组。每个子值数组的相应偏移量必须按顺序/递增。

示例布局：DenseUnion<f: Float32, i: Int32>#

对于联合数组 [{f=1.2}, null, {f=3.4}, {i=5}] 表示为：

* Length: 4, Null count: 0
* Types buffer:

  | Byte 0   | Byte 1      | Byte 2   | Byte 3   | Bytes 4-63            |
  |----------|-------------|----------|----------|-----------------------|
  | 0        | 0           | 0        | 1        | unspecified (padding) |

* Offset buffer:

  | Bytes 0-3 | Bytes 4-7   | Bytes 8-11 | Bytes 12-15 | Bytes 16-63           |
  |-----------|-------------|------------|-------------|-----------------------|
  | 0         | 1           | 2          | 0           | unspecified (padding) |

* Children arrays:
  * Field-0 array (f: Float32):
    * Length: 3, Null count: 1
    * Validity bitmap buffer: 00000101

    * Value Buffer:

      | Bytes 0-11     | Bytes 12-63           |
      |----------------|-----------------------|
      | 1.2, null, 3.4 | unspecified (padding) |


  * Field-1 array (i: Int32):
    * Length: 1, Null count: 0
    * Validity bitmap buffer: Not required

    * Value Buffer:

      | Bytes 0-3 | Bytes 4-63            |
      |-----------|-----------------------|
      | 5         | unspecified (padding) |

稀疏联合#

稀疏联合(Sparse Union)具有与密集联合相同的结构，但省略了偏移量数组。在这种情况下，子数组的长度都等于联合的长度。

虽然与密集联合相比，稀疏联合可能会使用更多的空间，但它在某些用例中可能具有一些优势：

  • 在某些用例中，稀疏联合更适合向量化表达式求值。

  • 等长子数组可以通过仅定义类型数组来解释为联合。

示例布局：SparseUnion<i: Int32, f: Float32, s: VarBinary>#

对于联合数组 [{i=5}, {f=1.2}, {s='joe'}, {f=3.4}, {i=4}, {s='mark'}] 表示为：

* Length: 6, Null count: 0
* Types buffer:

 | Byte 0     | Byte 1      | Byte 2      | Byte 3      | Byte 4      | Byte 5       | Bytes  6-63           |
 |------------|-------------|-------------|-------------|-------------|--------------|-----------------------|
 | 0          | 1           | 2           | 1           | 0           | 2            | unspecified (padding) |

* Children arrays:

  * i (Int32):
    * Length: 6, Null count: 4
    * Validity bitmap buffer:

      | Byte 0 (validity bitmap) | Bytes 1-63            |
      |--------------------------|-----------------------|
      | 00010001                 | 0 (padding)           |

    * Value buffer:

      | Bytes 0-3   | Bytes 4-7   | Bytes 8-11  | Bytes 12-15 | Bytes 16-19 | Bytes 20-23  | Bytes 24-63           |
      |-------------|-------------|-------------|-------------|-------------|--------------|-----------------------|
      | 5           | unspecified | unspecified | unspecified | 4           |  unspecified | unspecified (padding) |

  * f (Float32):
    * Length: 6, Null count: 4
    * Validity bitmap buffer:

      | Byte 0 (validity bitmap) | Bytes 1-63            |
      |--------------------------|-----------------------|
      | 00001010                 | 0 (padding)           |

    * Value buffer:

      | Bytes 0-3    | Bytes 4-7   | Bytes 8-11  | Bytes 12-15 | Bytes 16-19 | Bytes 20-23 | Bytes 24-63           |
      |--------------|-------------|-------------|-------------|-------------|-------------|-----------------------|
      | unspecified  | 1.2         | unspecified | 3.4         | unspecified | unspecified | unspecified (padding) |

  * s (`VarBinary`)
    * Length: 6, Null count: 4
    * Validity bitmap buffer:

      | Byte 0 (validity bitmap) | Bytes 1-63            |
      |--------------------------|-----------------------|
      | 00100100                 | 0 (padding)           |

    * Offsets buffer (Int32)

      | Bytes 0-3  | Bytes 4-7   | Bytes 8-11  | Bytes 12-15 | Bytes 16-19 | Bytes 20-23 | Bytes 24-27 | Bytes 28-63            |
      |------------|-------------|-------------|-------------|-------------|-------------|-------------|------------------------|
      | 0          | 0           | 0           | 3           | 3           | 3           | 7           | unspecified (padding)  |

    * Values buffer:

      | Bytes 0-6  | Bytes 7-63            |
      |------------|-----------------------|
      | joemark    | unspecified (padding) |

只有与类型索引对应的数组槽位会被考虑。所有“未选中”的值都被忽略，可以是任何语义上正确的数组值。

空值布局#

我们为所有值都为空的 Null 数据类型提供了一种简化的、内存高效的布局。在这种情况下，不会分配任何内存缓冲区。

字典编码布局#

字典编码是一种数据表示技术，通过引用通常由唯一值组成的字典中的整数来表示值。当数据中有大量重复值时，这种方法可能非常有效。

任何数组都可以进行字典编码。字典作为数组的一个可选属性存储。当一个字段被字典编码时，值由非负整数数组表示，这些整数代表字典中值的索引。字典编码数组的内存布局与原始整数布局相同。字典被视为具有自己相应布局的单独列式数组。

例如，你可以有以下数据：

type: VarBinary

['foo', 'bar', 'foo', 'bar', null, 'baz']

在字典编码形式中，这可能显示为：

data VarBinary (dictionary-encoded)
   index_type: Int32
   values: [0, 1, 0, 1, null, 2]

dictionary
   type: VarBinary
   values: ['foo', 'bar', 'baz']

注意，字典允许包含重复值或空值：

data VarBinary (dictionary-encoded)
   index_type: Int32
   values: [0, 1, 3, 1, 4, 2]

dictionary
   type: VarBinary
   values: ['foo', 'bar', 'baz', 'foo', null]

这些数组的空值计数仅由其索引的有效性位图决定，与字典中的任何空值无关。

由于在某些情况下无符号整数可能更难处理（例如在JVM中），我们建议在表示字典索引时优先使用有符号整数而不是无符号整数。此外，除非应用程序需要，否则我们建议避免使用64位无符号整数索引。

我们在下面进一步讨论与序列化相关的字典编码。

行程-结束编码布局#

行程-结束编码（Run-end encoding，REE）是行程长度编码（run-length encoding，RLE）的一种变体。这些编码非常适合表示包含相同值序列的数据，称为行程(runs)。在行程-结束编码中，每个行程由一个值和一个整数表示，该整数给出数组中行程结束的索引。

任何数组都可以进行行程-结束编码。行程-结束编码的数组本身没有缓冲区，但有两个子数组。第一个子数组称为行程结束数组，保存16位、32位或64位有符号整数。实际的行程值保存在第二个子数组中。为了确定字段名称和模式，这些子数组被规定了标准名称分别为 run_ends 和 values。

第一个子数组中的值表示从第一个到当前行程的所有行程的累积长度，即当前行程结束的逻辑索引。这允许使用二分搜索从逻辑索引相对高效地进行随机访问。单个行程的长度可以通过减去两个相邻值来确定。（与此相反，行程长度编码直接表示行程的长度，并且随机访问效率较低。）

备注

因为 run_ends 子数组不能有空值，所以合理的考虑是为什么 run_ends 是一个子数组而不是像可变大小列表布局的偏移量那样的缓冲区。这种布局被考虑过，但最终决定使用子数组。

子数组允许我们保持与父数组相关的“逻辑长度”（解码长度）和与子数组相关的“物理长度”（行程结束的数量）。如果 run_ends 是父数组中的一个缓冲区，那么缓冲区的大小将与数组的长度无关，这将会造成混淆。

行程(run)的长度必须至少为1。这意味着行程结束数组中的值都是正数，并且严格按照升序排列。行程结束不能为空。

REE父数组没有有效性位图，其空值计数字段应始终为 0。空值被编码为值为 null 的行程。

例如，你可以有以下数据：

type: Float32
[1.0, 1.0, 1.0, 1.0, null, null, 2.0]

在行程-结束编码形式中，这可能显示为：

* Length: 7, Null count: 0
* Child Arrays:

  * run_ends (Int32):
    * Length: 3, Null count: 0 (Run Ends cannot be null)
    * Validity bitmap buffer: Not required (if it exists, it should be all 1s)
    * Values buffer

      | Bytes 0-3   | Bytes 4-7   | Bytes 8-11  | Bytes 12-63           |
      |-------------|-------------|-------------|-----------------------|
      | 4           | 6           | 7           | unspecified (padding) |

  * values (Float32):
    * Length: 3, Null count: 1
    * Validity bitmap buffer:

      | Byte 0 (validity bitmap) | Bytes 1-63            |
      |--------------------------|-----------------------|
      | 00000101                 | 0 (padding)           |

    * Values buffer

      | Bytes 0-3   | Bytes 4-7   | Bytes 8-11  | Bytes 12-63           |
      |-------------|-------------|-------------|-----------------------|
      | 1.0         | unspecified | 2.0         | unspecified (padding) |

每种布局的缓冲区列表#

为了避免歧义，我们提供了每种布局的内存缓冲区的顺序和类型的列表。

表 1 Buffer 布局#

Layout Type

Buffer 0

Buffer 1

Buffer 2

Variadic Buffers

Primitive

validity

data

Variable Binary

validity

offsets

data

Variable Binary View

validity

views

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)

Run-end encoded