箭头列式格式#

版本：1.4

另请参阅

自版本 1.0.0 以来对箭头列式格式的补充

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

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

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

用于顺序访问（扫描）的数据邻接性
O(1)（常数时间）随机访问
SIMD 和矢量化友好
无需“指针混排”即可重新定位，允许在共享内存中实现真正的零拷贝访问

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

术语#

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

数组或向量：具有已知长度的、所有值都具有相同类型的值序列。这些术语在不同的箭头实现中可互换使用，但本文档中使用“数组”。
槽：数组中某个特定数据类型的单个逻辑值
缓冲区或连续内存区域：具有给定长度的顺序虚拟地址空间。任何字节都可以通过小于区域长度的单个指针偏移量访问。
物理布局：数组的底层内存布局，不考虑任何值语义。例如，32 位有符号整数数组和 32 位浮点数数组具有相同的布局。
父数组和子数组：用于表达嵌套类型结构中物理值数组之间关系的名称。例如，List<T> 类型的父数组具有 T 类型的数组作为其子数组（有关列表的更多信息，请参见下文）。
基本类型：没有子类型的类型。这包括固定位宽、可变大小二进制和空类型等类型。
嵌套类型：其完整结构取决于一个或多个其他子类型的类型。两个完全指定的嵌套类型相等当且仅当它们的子类型相等。例如，List<U> 与 List<V> 不同当且仅当 U 和 V 是不同的类型。
逻辑类型：面向应用程序的语义值类型，使用某种物理布局实现。例如，十进制值存储为 16 字节的固定大小二进制布局。类似地，字符串可以存储为 List<1-byte>。时间戳可以存储为 64 位固定大小布局。

物理内存布局#

数组由一些元数据和数据定义

逻辑数据类型。
缓冲区序列。
长度为 64 位有符号整数。允许实现限制为 32 位长度，有关更多信息，请参见下文。
空计数为 64 位有符号整数。
可选的字典，用于字典编码数组。

嵌套数组还具有这些项目的序列，称为子数组。

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

基本（固定大小）：每个值都具有相同字节或位宽的值序列
可变大小二进制：每个值都具有可变字节长度的值序列。支持此布局的两种变体使用 32 位和 64 位长度编码。
可变大小二进制的视图：每个值都具有可变字节长度的值序列。与可变大小二进制不同，此布局的值分布在可能多个缓冲区中，而不是密集且顺序地打包在一个缓冲区中。
固定大小列表：嵌套布局，其中每个值都具有相同数量的来自子数据类型的元素。
可变大小列表：嵌套布局，其中每个值都是来自子数据类型的可变长度值序列。支持此布局的两种变体使用 32 位和 64 位长度编码。
可变大小列表的视图：嵌套布局，其中每个值都是来自子数据类型的可变长度值序列。此布局与可变大小列表的不同之处在于它有一个额外的缓冲区，其中包含每个列表值的尺寸。这消除了对偏移量缓冲区的约束——它不需要按顺序排列。
结构：嵌套布局，由一组命名子字段组成，每个字段都具有相同的长度，但类型可能不同。
稀疏和密集联合：嵌套布局，表示值序列，每个值都可以从子数组类型的集合中选择类型。
字典编码：布局由整数序列（任何位宽）组成，这些整数表示字典中的索引，字典可以是任何类型。
运行结束编码 (REE)：嵌套布局，由两个子数组组成，一个表示值，另一个表示对应值运行的逻辑索引结束的位置。
空：所有空值的序列，具有空逻辑类型

箭头列式内存布局仅适用于数据，而不适用于元数据。实现可以自由地以对它们最方便的任何形式在内存中表示元数据。我们使用 Flatbuffers 以与实现无关的方式处理元数据序列化，如下所述。

缓冲区对齐和填充#

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

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

数字数组中的元素将保证通过对齐访问检索。
在某些体系结构上，对齐可以帮助限制部分使用的缓存行。

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

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

数组长度#

数组长度在箭头元数据中表示为 64 位有符号整数。即使箭头实现仅支持最大 32 位有符号整数的长度，也认为它是有效的。如果在多语言环境中使用箭头，建议将长度限制为 2 ³¹ - 1 个元素或更少。可以使用多个数组块来表示更大的数据集。

空计数#

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

有效性位图#

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

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

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

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

我们使用最低有效位 (LSB) 编号（也称为位端序）。这意味着在一组 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 数组的使用者应该准备好处理这两种可能性。

嵌套类型数组（除了上面提到的联合类型）具有自己的顶层有效性位图和空值计数，无论其子数组的空值计数和有效位如何。

空值的数组槽不需要具有特定值；任何“屏蔽”的内存可以具有任何值，并且不需要清零，尽管实现通常选择将空值的内存清零。

固定大小的原始布局#

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

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

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

示例布局：Int32 数组

例如，一个 int32 的原始数组

[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) |

示例布局：非空 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 个或多个字节。虽然原始数组只有一个值缓冲区，但可变大小的二进制数组具有一个**偏移量**缓冲区和一个**数据**缓冲区。

偏移量缓冲区包含 length + 1 个有符号整数（32 位或 64 位，具体取决于逻辑类型），它们编码数据缓冲区中每个槽的起始位置。每个槽中值的长度使用该槽索引处的偏移量与后续偏移量之间的差值计算。例如，槽 j 的位置和长度计算如下

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

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

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

通常，偏移量数组中的第一个槽为 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) |

可变大小的二进制视图布局#

Arrow 版本 1.4 中新增：列式格式

此布局中的每个值都包含 0 个或多个字节。这些字节的位置使用一个**视图**缓冲区来指示，该缓冲区可能指向多个潜在的**数据**缓冲区之一，或者可能包含内联字符。

视图缓冲区包含 length 个视图结构，其布局如下

* 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 填充。

在长字符串情况下，缓冲区索引指示哪个数据缓冲区存储数据字节，偏移量指示数据字节在该缓冲区中的起始位置。缓冲区索引 0 指的是第一个数据缓冲区，即**在**有效性缓冲区和视图缓冲区之后的第一个缓冲区。半开区间 [offset, offset + length) 必须完全包含在指示的缓冲区内。字符串的前四个字节的副本存储在内联前缀中，在长度之后。此前缀使字符串比较的快速路径变得有利可图，字符串比较通常在头四个字节内确定。

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

此布局改编自慕尼黑工业大学的 UmbraDB。

请注意，此布局使用一个额外的缓冲区来存储 Arrow C 数据接口中的可变缓冲区长度。

可变大小的列表布局#

列表是一个嵌套类型，在语义上类似于可变大小的二进制。有两种列表布局变体——“列表”和“列表视图”——每种变体都可以由 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 布局#

Arrow 版本 1.4 中新增：列式格式

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

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

每个列表视图值，包括空值，都必须保证以下不变式

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

列表视图类型指定为 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>`` 数组

我们继续使用 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 中的值存储在值数组的 N 长切片中，从偏移量 j * 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) |

结构有效性#

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

因此，要了解特定子条目是否有效，必须对两个有效性位图（结构数组的和子数组的）中的相应位进行逻辑 AND 操作。

这在上面的示例中得到了说明，其中一个子数组对空结构具有有效条目 'alice'，但它被结构数组的有效性位图“隐藏”了。但是，当独立处理时，子数组的相应条目将是非空的。

联合布局#

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

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

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

密集联合#

密集联合表示一个混合类型数组，每个值有 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) |

稀疏联合#

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

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

在某些用例中，稀疏联合更容易进行向量化表达式求值。
等长数组可以通过仅定义类型数组来解释为联合。

示例布局：``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 位无符号整数索引，除非应用程序需要它们。

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

运行结束编码布局#

Arrow 版本中的新增功能：列式格式 1.3

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

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

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

注意

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

子数组允许我们将“逻辑长度”（解码长度）与父数组相关联，并将“物理长度”（运行结束的数量）与子数组相关联。如果run_ends是父数组中的缓冲区，那么缓冲区的大小将与数组的长度无关，这会令人困惑。

运行的长度必须至少为 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) |

每个布局的缓冲区列表#

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

缓冲区布局#
布局类型	缓冲区 0	缓冲区 1	缓冲区 2	可变参数缓冲区
原始	有效性	数据
可变二进制	有效性	偏移量	数据
可变二进制视图	有效性	视图		数据
列表	有效性	偏移量
固定大小列表	有效性
结构体	有效性
稀疏联合	类型 ID
密集联合	类型 ID	偏移量
空
字典编码	有效性	数据（索引）
运行结束编码

逻辑类型#

在Schema.fbs中定义了 Arrow 列式格式支持的内置逻辑类型。每个逻辑类型都使用上述物理布局之一。嵌套逻辑类型可能具有不同的物理布局，具体取决于类型的特定实现。

我们不会在本文件中详细介绍逻辑类型定义，因为我们认为Schema.fbs是权威的。

序列化和进程间通信 (IPC)#

列式格式中序列化数据的基本单位是“记录批”。从语义上讲，记录批是数组的有序集合，称为其字段，每个数组的长度彼此相同，但数据类型可能不同。记录批的字段名称和类型共同构成批的模式。

在本节中，我们定义了一种协议，用于将记录批序列化为二进制有效负载流，并从这些有效负载中重建记录批，而无需内存复制。

列式 IPC 协议使用以下类型的二进制消息的单向流

模式
记录批
字典批

我们指定了一种所谓的封装 IPC 消息格式，其中包括一个序列化 Flatbuffer 类型以及一个可选的消息主体。在描述如何序列化每个组成 IPC 消息类型之前，我们定义了此消息格式。

封装消息格式#

对于简单的流式传输和基于文件的序列化，我们定义了一种用于进程间通信的“封装”消息格式。此类消息可以通过仅检查消息元数据来“反序列化”为内存中的 Arrow 数组对象，而无需复制或移动任何实际数据。

封装的二进制消息格式如下

一个 32 位延续指示器。值0xFFFFFFFF表示有效消息。此组件是在版本 0.15.0 中引入的，部分是为了解决 Flatbuffers 的 8 字节对齐要求
一个 32 位小端长度前缀，指示元数据大小
使用Message.fbs中定义的Message类型作为消息元数据
填充字节到 8 字节边界
消息主体，其长度必须是 8 字节的倍数

从图示上看，我们有

<continuation: 0xFFFFFFFF>
<metadata_size: int32>
<metadata_flatbuffer: bytes>
<padding>
<message body>

完整的序列化消息必须是 8 字节的倍数，以便消息可以在流之间重新定位。否则，元数据和消息主体之间的填充量可能是不确定的。

metadata_size包括Message的大小以及填充。metadata_flatbuffer包含一个序列化的Message Flatbuffer 值，该值在内部包含

版本号
特定消息值（Schema、RecordBatch或DictionaryBatch之一）
消息主体的大小
一个custom_metadata字段，用于任何应用程序提供的元数据

从输入流中读取时，通常会首先解析和验证Message元数据以获取主体大小。然后可以读取主体。

模式消息#

Flatbuffers 文件 Schema.fbs 包含所有内置逻辑数据类型的定义以及 Schema 元数据类型，该类型表示给定记录批次的模式。模式由一个有序的字段序列组成，每个字段都有一个名称和类型。序列化后的 Schema 不包含任何数据缓冲区，只包含类型元数据。

The Field Flatbuffers 类型包含单个数组的元数据。这包括

字段的名称
字段的逻辑类型
字段在语义上是否可为空。虽然这与数组的物理布局无关，但许多系统区分可空字段和不可空字段，我们希望允许它们保留这些元数据以实现忠实的模式往返。
对于嵌套类型，一个子 Field 值的集合
一个 dictionary 属性，指示字段是否为字典编码。如果是，则分配一个字典“id”以允许将后续字典 IPC 消息与相应的字段匹配。

我们还提供模式级和字段级的 custom_metadata 属性，允许系统插入自己的应用程序定义的元数据以自定义行为。

RecordBatch 消息#

RecordBatch 消息包含与由模式确定的物理内存布局相对应的实际数据缓冲区。此消息的元数据提供了每个缓冲区的位置和大小，允许使用指针算术重建 Array 数据结构，因此无需内存复制。

记录批次的序列化形式如下

The data header，定义为 Message.fbs 中的 RecordBatch 类型。
The body，一个扁平的内存缓冲区序列，以端到端的方式写入，并进行适当的填充以确保至少 8 字节对齐

数据头包含以下内容

记录批次中每个扁平化字段的长度和空计数
记录批次主体中每个组成 Buffer 的内存偏移量和长度

字段和缓冲区通过对记录批次中字段的先序深度优先遍历进行扁平化。例如，让我们考虑以下模式

col1: Struct<a: Int32, b: List<item: Int64>, c: Float64>
col2: Utf8

此模式的扁平化版本为

FieldNode 0: Struct name='col1'
FieldNode 1: Int32 name='a'
FieldNode 2: List name='b'
FieldNode 3: Int64 name='item'
FieldNode 4: Float64 name='c'
FieldNode 5: Utf8 name='col2'

对于生成的缓冲区，我们将有以下内容（参考上表）

buffer 0: field 0 validity
buffer 1: field 1 validity
buffer 2: field 1 values
buffer 3: field 2 validity
buffer 4: field 2 offsets
buffer 5: field 3 validity
buffer 6: field 3 values
buffer 7: field 4 validity
buffer 8: field 4 values
buffer 9: field 5 validity
buffer 10: field 5 offsets
buffer 11: field 5 data

The Buffer Flatbuffers 值描述了内存片段的位置和大小。通常，这些值相对于下面定义的封装消息格式进行解释。

The size 字段 Buffer 不需要考虑填充字节。由于此元数据可用于在库之间通信内存指针地址，因此建议将 size 设置为实际内存大小，而不是填充大小。

可变参数缓冲区#

Arrow 版本 1.4 中新增：列式格式

某些类型（如 Utf8View）使用可变数量的缓冲区表示。对于预先排序的扁平化逻辑模式中的每个此类字段，variadicBufferCounts 中将有一个条目，指示当前 RecordBatch 中属于该字段的可变参数缓冲区的数量。

例如，考虑以下模式

col1: Struct<a: Int32, b: BinaryView, c: Float64>
col2: Utf8View

此模式有两个具有可变参数缓冲区的字段，因此 variadicBufferCounts 在每个 RecordBatch 中将有两个条目。对于具有 variadicBufferCounts = [3, 2] 的此模式的 RecordBatch，扁平化缓冲区将为

buffer 0:  col1    validity
buffer 1:  col1.a  validity
buffer 2:  col1.a  values
buffer 3:  col1.b  validity
buffer 4:  col1.b  views
buffer 5:  col1.b  data
buffer 6:  col1.b  data
buffer 7:  col1.b  data
buffer 8:  col1.c  validity
buffer 9:  col1.c  values
buffer 10: col2    validity
buffer 11: col2    views
buffer 12: col2    data
buffer 13: col2    data

字节序 (Endianness)#

Arrow 格式默认情况下是小端序。

序列化后的模式元数据有一个字节序字段，指示 RecordBatches 的字节序。通常，这是生成 RecordBatch 的系统的字节序。主要用例是在具有相同字节序的系统之间交换 RecordBatches。最初，当尝试读取字节序与底层系统不匹配的模式时，我们将返回错误。参考实现侧重于小端序，并为此提供测试。最终，我们可能会通过字节交换提供自动转换。

IPC 流格式#

我们为记录批次提供了一个流协议或“格式”。它被呈现为一系列封装的消息，每个消息都遵循上述格式。模式首先出现在流中，并且对于所有后续的记录批次都是相同的。如果模式中的任何字段是字典编码的，则将包含一个或多个 DictionaryBatch 消息。 DictionaryBatch 和 RecordBatch 消息可以交错，但在 RecordBatch 中使用任何字典键之前，它应该在 DictionaryBatch 中定义。

<SCHEMA>
<DICTIONARY 0>
...
<DICTIONARY k - 1>
<RECORD BATCH 0>
...
<DICTIONARY x DELTA>
...
<DICTIONARY y DELTA>
...
<RECORD BATCH n - 1>
<EOS [optional]: 0xFFFFFFFF 0x00000000>

注意

交错字典和记录批次的边缘情况发生在记录批次包含完全为空的字典编码数组时。在这种情况下，编码列的字典可能会出现在第一个记录批次之后。

当流读取器实现读取流时，在每条消息之后，它可能会读取接下来的 8 个字节以确定流是否继续以及后续消息元数据的大小。读取消息 flatbuffer 后，您就可以读取消息主体。

流写入器可以通过写入包含 4 字节延续指示符 (0xFFFFFFFF) 的 8 个字节，后跟 0 元数据长度 (0x00000000) 或关闭流接口来发出流结束 (EOS) 信号。我们建议将“.arrows”文件扩展名用于流格式，尽管在许多情况下，这些流永远不会存储为文件。

IPC 文件格式#

我们定义了一个支持随机访问的“文件格式”，它是流格式的扩展。文件以魔术字符串 ARROW1（加上填充）开头和结尾。文件中接下来的内容与流格式相同。在文件末尾，我们写入一个页脚，其中包含模式的冗余副本（它是流格式的一部分），以及文件中每个数据块的内存偏移量和大小。这使得能够随机访问文件中任何记录批次。有关文件页脚的精确细节，请参阅 File.fbs。

示意性地，我们有

<magic number "ARROW1">
<empty padding bytes [to 8 byte boundary]>
<STREAMING FORMAT with EOS>
<FOOTER>
<FOOTER SIZE: int32>
<magic number "ARROW1">

在文件格式中，没有要求字典键在 RecordBatch 中使用之前，应该在 DictionaryBatch 中定义，只要这些键在文件中定义即可。此外，对于每个字典 ID，拥有多个非增量字典批次是无效的（即不支持字典替换）。增量字典按它们在文件页脚中出现的顺序应用。我们建议将“.arrow”扩展名用于使用此格式创建的文件。请注意，使用此格式创建的文件有时被称为“Feather V2”或使用“.feather”扩展名，名称和扩展名源自“Feather (V1)”，它是 Arrow 项目早期为 Python (pandas) 和 R 提供语言无关的快速数据帧存储的概念验证。

字典消息#

字典在流和文件格式中被写入为一系列记录批次，每个批次只有一个字段。因此，一系列记录批次的完整语义模式由模式以及所有字典组成。字典类型在模式中找到，因此有必要先读取模式以确定字典类型，以便能够正确地解释字典

table DictionaryBatch {
  id: long;
  data: RecordBatch;
  isDelta: boolean = false;
}

消息元数据中的字典 id 可以在模式中引用一次或多次，因此字典甚至可以用于多个字段。有关字典编码数据的语义的更多信息，请参阅字典编码布局部分。

字典 isDelta 标志允许为将来的记录批次物化扩展现有字典。具有 isDelta 设置的字典批次表示其向量应与具有相同 id 的任何先前批次的向量连接。在一个编码一列的流中，字符串列表 ["A", "B", "C", "B", "D", "C", "E", "A"]，使用增量字典批次可以采用以下形式

<SCHEMA>
<DICTIONARY 0>
(0) "A"
(1) "B"
(2) "C"

<RECORD BATCH 0>
0
1
2
1

<DICTIONARY 0 DELTA>
(3) "D"
(4) "E"

<RECORD BATCH 1>
3
2
4
0
EOS

或者，如果 isDelta 设置为 false，则字典将替换具有相同 ID 的现有字典。使用与上面相同的示例，另一种编码可以是

<SCHEMA>
<DICTIONARY 0>
(0) "A"
(1) "B"
(2) "C"

<RECORD BATCH 0>
0
1
2
1

<DICTIONARY 0>
(0) "A"
(1) "C"
(2) "D"
(3) "E"

<RECORD BATCH 1>
2
1
3
0
EOS

自定义应用程序元数据#

我们在三个级别提供一个 custom_metadata 字段，以提供一种机制供开发人员在 Arrow 协议消息中传递特定于应用程序的元数据。这包括 Field、Schema 和 Message。

冒号符号 : 用作命名空间分隔符。它可以在一个键中使用多次。

The ARROW 模式是 custom_metadata 字段中用于 Arrow 内部使用的保留命名空间。例如，ARROW:extension:name。

扩展类型#

用户定义的“扩展”类型可以通过在Field元数据结构中的custom_metadata中设置某些KeyValue对来定义。这些扩展键是

'ARROW:extension:name' 用于标识自定义数据类型的字符串名称。我们建议您为扩展类型名称使用“命名空间”样式前缀，以最大程度地减少在同一应用程序中使用多个 Arrow 读取器和写入器时发生冲突的可能性。例如，使用myorg.name_of_type而不是简单的name_of_type
'ARROW:extension:metadata' 用于ExtensionType的序列化表示，该表示对于重建自定义类型是必要的

注意

以arrow.开头的扩展名称保留给规范扩展类型，它们不应用于第三方扩展类型。

此扩展元数据可以注释任何内置的 Arrow 逻辑类型。目的是，不支持扩展类型的实现仍然可以处理底层数据。例如，一个 16 字节的 UUID 值可以嵌入在FixedSizeBinary(16)中，不支持此扩展类型的实现仍然可以处理底层二进制值并将custom_metadata传递到后续的 Arrow 协议消息中。

扩展类型可能使用也可能不使用'ARROW:extension:metadata'字段。让我们考虑一些示例扩展类型

uuid 表示为FixedSizeBinary(16)，元数据为空
latitude-longitude 表示为struct<latitude: double, longitude: double>，元数据为空
tensor（多维数组）存储为Binary值，并具有序列化元数据，指示每个值的类型和形状。这可以是类似 JSON 的{'type': 'int8', 'shape': [4, 5]}，用于 4x5 单元格张量。
trading-time 表示为Timestamp，并具有序列化元数据，指示数据对应的市场交易日历

另请参阅

规范扩展类型

实现指南#

执行引擎（或框架、或 UDF 执行器、或存储引擎等）可以仅实现 Arrow 规范的子集，或者在以下约束条件下对其进行扩展

实现规范的子集#

**如果仅生成（而不是使用）箭头向量**：可以实现向量规范的任何子集及其相应的元数据。
**如果使用和生成向量**：需要支持向量的最小子集。生成向量子集及其相应的元数据始终是可以的。使用向量时，至少应将不支持的输入向量转换为支持的子集（例如，将 Timestamp.millis 转换为 timestamp.micros 或将 int32 转换为 int64）。

可扩展性#

执行引擎实现者还可以使用他们自己的向量扩展其内部内存表示，只要这些向量从不暴露。在将数据发送到期望 Arrow 数据的另一个系统之前，应将这些自定义向量转换为 Arrow 规范中存在的类型。