Apache Arrow | Primitive Layouts

Fixed Size Primitive Layout

固定大小的基础数据类型布局,指内存或数据结构中，大小固定的基本类型的排列方式。

原始列表示一个值数组，其中每个值具有相同的物理大小（以字节为单位）。使用固定大小原始布局的数据类型例如有：有符号和无符号整数类型、浮点数、布尔值、小数以及时间类型数据。

原始数据示例:

• column 1 是整数列，没有空值。
• column 2 是浮点数列，有一个空值（null）。

内存中的物理布局:

• column 1（整数列）
  • Validity bitmap buffer（有效性位图缓冲区）：显示为 None，说明这一列没有空值，所有数据都是有效的，所以不需要额外的位图来记录有效性状态。
  • Values buffer（值缓冲区）：存储了这列中所有整数的实际值 [1, 3, 9, 9, 2]，这些值是连续存储的，占用固定大小的空间（如每个整数4字节）。
• column 2（浮点数列）
  • Validity bitmap buffer（有效性位图缓冲区）：值是 00010111，这是一个二进制序列，用来标记每个值是否有效（1表示有效，0表示无效，即null）。
    • 从右往左数（通常位图是从最低位开始代表第一个元素），4 个元素对应的位是：
      • 第1个值 1.2 — bit为1，有效
      • 第2个值 3.4 — bit为1，有效
      • 第3个值 9.0 — bit为1，有效
      • 第4个值 null — bit为0，无效
      • 第5个值 2.9 — bit为1，有效
  • Values buffer（值缓冲区）：存储了非空值 [1.2, 3.4, 9.0, _, 2.9]，第4个元素对应的值空缺（用 _ 表示），因为它是空值，具体位置不存储实际数据或可能用某种占位符代替。

总结：

• 固定大小的原始布局中，每个元素占用相同大小的字节，值直接顺序存储在值缓冲区中。
• 对于有空值的列，用一个有效性位图缓冲区用二进制位标识每一行数据是否有效，节省存储空间并方便快速判断。
• 没有空值的列则完全不需要有效性位图，直接存储所有值。
• 这个布局可以高效地存储和访问大量原始数据类型（整数、浮点数等），并支持空值管理。

布尔类型的数据使用一种原始布局表示，其中数据是以位（bit）而不是字节（byte）进行编码的。这意味着物理布局包括一个值位图缓冲区（values bitmap buffer），并且可能还包含一个有效性位图缓冲区（validity bitmap buffer）。

• 左边的column 10列包含布尔值：True、True、False、null、False、True。
• 右边的Validity bitmap buffer用二进制 00110111 表示哪些值是有效的（1表示有效，0表示无效/null）。
• Values bitmap buffer用二进制 11000100 表示对应位置的布尔值，即True或False的实际值。

Variable length binary and string

可变长度的二进制和字符串，指二进制数据和字符串，其长度不是固定的，可以变化。

与固定大小的原始布局相比，可变长度布局允许表示一个数组，其中每个元素的字节大小可以不同。这种布局用于二进制和字符串数据。

二进制或字符串列中所有元素的字节会连续存储在单个缓冲区或内存区域中。为了确定每个元素在列中的起始和结束位置，物理布局还包括整型偏移量。偏移量缓冲区的长度总是比数组元素数量多一个。最后两个偏移量定义了最后一个二进制或字符串元素的起始和结束位置。

二进制和字符串数据类型共享相同的物理布局，它们唯一的区别是字符串类型的数组被假设包含有效的 UTF-8 字符串数据。

二进制/字符串与大二进制/字符串之间的区别在于偏移量的数据类型。前者使用 int32，后者使用 int64。

使用 32 位偏移量的数据类型的限制是每个数组的最大大小为 2GB。对于更大的数据，仍可以使用非大类型变体，但这时需要多个数据块（chunk）来存储。

原始字符串数据:

• 这是一个字符串列，其中包含了五个元素。
• 第四个元素是空值（null）。

内存中的布局结构:

• Validity bitmap buffer（有效性位图缓冲区） : 00010111
  • 用二进制位表示每个元素是否有效（1表示有效，0表示无效）。
  • 这里的每位代表对应行是否有有效字符串：
    • 第1个："python" —— 1（有效）
    • 第2个："data" —— 1（有效）
    • 第3个："conference" —— 1（有效）
    • 第4个：null —— 0（无效）
    • 第5个："Berlin" —— 1（有效）
• Offsets buffer（偏移量缓冲区） : [0, 6, 10, 20, 20, 26]
  • 记录每个字符串的起始和结束字节位置。
  • 偏移量数量比元素多一个，最后两个偏移量表示最后元素的结束位置。
  • 具体分析：
    • 第1个字符串 "python" 从字节0开始，到字节6止（长度6）
    • 第2个字符串 "data" 从字节6开始，到字节10止（长度4）
    • 第3个字符串 "conference" 从字节10开始，到字节20止（长度10）
    • 第4个字符串是null，对应的起止位置都是20（长度0）
    • 第5个字符串 "Berlin" 从字节20开始，到字节26止（长度6）
• Values buffer（值缓冲区） : "pythondataconferenceBerlin"
  • 所有有效字符串的字符数据连接成一个连续的字符序列存储。
  • 空值的位置没有对应字符存储（长度为0），但可以根据偏移量辨识出来。

总结：

• 字符串数据不再是固定字节数，因此需要用偏移量数组来标记每个字符串的位置和长度。
• 所有字符串的数据连成一个大字符串块存储在值缓冲区中。
• 有效性位图记录哪些字符串是有效，哪些是空值，方便快速过滤和访问。
• 这种布局使得存储和访问不同长度的字符串变得高效且紧凑。

Variable length binary and string view

可变长度二进制和字符串视图，指对可变长度二进制或字符串数据的视图或映射，通常是一种只读或者轻量级访问方式。

这种布局是可变长度二进制布局的一个替代方案，改编自慕尼黑工业大学（TU Munich）的 UmbraDB，并且类似于 DuckDB 和 Velox 中使用的字符串布局（有时也被称为“German strings”）。

与传统的二进制和字符串布局相比，主要区别在于“views buffer”（视图缓冲区）。该缓冲区包含字符串的长度，以及字符串本身的字符——对于短字符串，它们以内联形式出现；对于较长字符串，视图缓冲区只包含字符串的前 4 个字节和一个偏移量，指向可能存在的多个数据缓冲区之一。由于它使用偏移量和长度来引用数据缓冲区，所有元素的字节不需要连续存储在单一缓冲区中。这使得可以对可变长度元素进行乱序写入到数组中。

这些特性对于高效的字符串处理非常重要。字符串的前缀（prefix）提供了一条有利且快速的路径，用于字符串比较，而字符串比较通常只需检查前四个字节。元素的选择是对固定宽度“views buffer”进行简单的“聚合”操作（gather），无需重写值缓冲区，从而提高了处理效率。

原始字符串数据:

• Column 5 有5个字符串：
  • "String longer than 12"
  • "Short"
  • null（空值）
  • "Short string"
  • "Another long string"
• Column 6 也有5个字符串：
  • "Another long string"
  • "String longer than 12"
  • null（空值）
  • "Short string"
  • "pythondataconference"

内存中的布局结构:

• Validity bitmap buffer（有效性位图缓冲区）
  • 以位（bit）形式标识每个元素是否有效（1 表示有效，0 表示无效或 null）。
  • 例如 Column 5 和 Column 6 有效性位图都是 00011011，对应第四个元素是 null（0）。
• Views buffer（视图缓冲区）
  • 视图缓冲区采用固定宽度结构，包含了每个字符串元素的元数据，关键字段包括：
    • length（长度）：字符串长度（单位是字节）
    • data（数据）：样例字符串或“短字符串”的字符
    • prefix（前缀）：字符串的前几个字节（用于快速比较）
    • buffer index（缓冲区索引）：指出字符串内容存储在哪个值缓冲区（values buffer）
    • offset（偏移）：字符串内容在对应缓冲区中的起始位置
  • Column 5 的举例说明：
    • 第一个元素 "String longer than 12" 长度是 21
      • 前缀为空（表示不是内联短字符串）
      • buffer index 是 0（对应第一个 values buffer）
      • offset 是 0（从缓冲区的起始位置开始）
    • 第二个元素 "Short" 长度是 5
      • 是短字符串，内联存储在数据字段，数据字段直接是 "Short"
      • buffer index 和 offset 对应空或不适用
    • 其他字符串按此类推。
  • Column 6 的举例说明：
    • 第一个元素 "Another long string" 长度为 19，存储在 buffer index 0，从 offset 21 开始。
    • 最后一个字符串 "pythondataconference" 存储在 buffer index 1，offset 0。
  • 由于 buffer index 和 offset 的存在，可以支持多个 values buffer，不需要所有字符串连续存储。
• Values buffers（值缓冲区）
  • 存储所有字符串数据的原始字符内容。
  • 多个缓冲区存在时，buffer index 用于区分是哪个缓冲区。
  • 例如，Column 5 只有一个缓冲区：
    • 存储 "String longer than 12Another long string" 连续字符串。
  • Column 6 则有两个缓冲区：
    • 第0缓冲区存储 "String longer than 12Another long string"
    • 第1缓冲区存储 "pythondataconferenceBerlin"

总结

• 有效性位图 标记哪些字符串是有效的，哪些是 null。
• 视图缓冲区 用固定宽度结构存储字符串长度、内联短字符串数据（节省空间）、字符串前缀、缓冲区索引、偏移量等元信息。
• 值缓冲区 是存储所有字符串字符数据的地方，可以存在多个，支持乱序访问和写入。
• 该设计减少了必须连续存储字符串带来的限制，提高了灵活性和并发处理能力。
• 前缀字段优化了字符串比较操作，通常只需检查前几个字节即可快速判定。

1. 布局结构的不同

• Variable length binary and string layout（变长二进制/字符串布局）

  • 使用**Offsets buffer（偏移量缓冲区）**记录每个字符串的起止位置，所有字符串的字节数据连续存储在一个或多个Values buffer中。
  • 偏移量数组长度是元素数加一，用来定义每个字符串的区间。
  • 所有字符串数据必须按顺序紧密排列存储。
  • 有效性通过Validity bitmap控制。

• Variable-size Binary View Layout（变长二进制视图布局，也称为string view布局）

  • 采用了一个新的结构称为Views buffer（视图缓冲区），用于存储每个字符串的元信息。
  • Views buffer 中每个元素是固定宽度的结构，包含：字符串长度、字符串前缀（prefix）、buffer index（数据缓冲区索引）、offset（偏移）、甚至可能直接内联存储短字符串数据。
  • 允许将字符串数据存储在多个不连续的Values buffers中，根据buffer index和offset定位具体字符串。
  • 不要求字符串数据连续存储，支持乱序写入。
  • 同样有Validity bitmap控制有效性。

2. 对字符串存储和访问的影响

• 变长二进制/字符串布局

  • 优点：实现简单，字符串按顺序存储，偏移量直接定位。
  • 缺点：字符串元素的访问写入时，必须维护串联的连续存储，不支持乱序插入或修改。
  • 对大数据或并发操作灵活性差。

• 视图布局

  • 由于视图缓冲区的固定宽度记录，可以方便地快速访问长度和前缀信息。
  • 允许字符串分散存储在多个缓冲区，且不必顺序写入。
  • 支持字符串的乱序写入和灵活的数据组织。
  • 前缀缓存加快字符串比较和处理效率。

3. 字符串处理优化

• 在视图布局中，字符串的前缀（prefix）被专门存储，用于快速字节级比较，这意味着对字符串的相等性或排序判断可以先比较前几个字节而不用完整访问字符串，大幅提升比较速度。

• 变长布局则没有这个前缀优化，比较字符串时需要访问完整字符串。

4. 总结比较

总结

• “Variable length binary and string layout” 更简单、直观，数据连续，适合顺序访问。
• “Variable-size Binary View Layout” 则是一个更灵活、更高效的方案，适合复杂应用，支持多缓冲区、乱序写入和前缀优化，特别在高性能数据库或分析系统中会用到。

如果你需要，我可以帮你整理一个更图文并茂的对比说明。

• https://arrow.apache.org/docs/format/Intro.html