Everything You Always Wanted To Do in Table Scan

technology
, , ,

大神Orri Erling关于TableScan的一篇文章，非常不错，所以全文翻译了。

What Is Table Scan

表扫描，表面上听起来似乎微不足道且乏味。只是简单地从头到尾读取一大堆记录，有什么特别的呢？索引和其他类型的物理设计不是更有趣吗？随着数据量的增长，列式表扫描变得越来越突出。列式扫描是一个相当安全的基线操作：写入数据的成本很低，读取它的成本是可预测的。使表扫描成为主要操作的另一个因素是数据仓库中无处不在的非规范化。这一点由于列表、映射和其他非第一范式数据的普遍使用而进一步加剧。

表扫描的理论和实践，主要是常识和系统性应用的原则：不要做额外的工作，总是批量地做你所做的工作。许多系统，如谷歌的BigQuery，都实现了这里概述的一些优化。然而，在大数据世界中，做到所有这些还远未普及，因此有必要将这些全部展示出来，并在Presto之上实现一个模型。我们在这里讨论的是ORC格式，但同样的原则也适用于被拆分成列的Parquet或JSON。

我们将演示分为几个部分：

  • 数据的逻辑结构以及要应用到其上的操作。产生结果所必需的严格步骤是什么？
  • 与简单实现相比，性能提升了多少？
  • 实现是如何工作的，存在哪些困难和权衡？
  • 执行的物理方面。我们何时受CPU限制，何时受IO限制？我们如何调度IO，以及在一个越来越关注分离存储的世界中，我们从中获得了什么？
  • 关于文件格式我们能说些什么？使用案例的演化压力是什么？元数据又如何？

理想的表扫描可以用以下基本原理来描述：

  • 不要物化不在结果中的数据
  • 只读取严格必要产生结果的数据
  • 尽早过滤，首先运行最有效的过滤器
  • 以可预测大小的块产生输出，并在固定内存中运行

这是逻辑方面。物理方面是关于如何最大限度地利用IO，读取正确的块大小，并提前于需求进行，以便数据在被访问之前已经到达。接下来，我们将从原则层面审视这个问题。在随后的文章中，我们将探讨物理实现的实际情况以及实现这些所需的要素。

Structure of ORC

ORC将数据划分为条带(stripes)和行组，通常每个组有10,000行，但如果行很宽，有时候可能更少。宽行的常见情况来自于映射和列表，这些可能每行有多达几千个嵌套值。一个条带是几个行组。任何特定列的编码在条带级别上设置。例如，一个列可能在一个条带中以字典形式编码，在另一个条带中以值序列的形式编码，这取决于数据的属性。

列由流(streams)组成。一个流对应于ORC文件中的一个连续区域。流由压缩块组成，这些块是高达256K的原始数据，可能会也可能不会使用流压缩如gzip、ZSTD或Snappy进行压缩。不同的流对列的不同方面进行编码，例如空值、长度和数据本身。

读取ORC文件涉及每个列的读取器。这些读取器形成了一个类层次结构。实际上，一些读取器封装了读取器的树，因为我们有像列表、映射和结构这样的结构化类型。

我们区分以下抽象超类：

列读取器（Column reader） — 封装了跟踪空值和长度的通用逻辑。
空包装器（Null wrapper） — 具有复杂内部结构的流的超类，适用于非空值。
重复（Repeated ） — 列表和映射的通用超类。这处理与一个顶层行有多个嵌套行相关的逻辑。
变体（Variant） — 封装了可能用于一个列的不同条带的选择的交替读取器。例如，字符串读取器是一个变体，它包装了直接和字典字符串读取器。

实际的流读取器对应于SQL数据类型，如数字和字符串。三种结构化类型，列表、映射和结构，包装了一个或多个任意类型的读取器。列表有一个用于重复数据的嵌套读取器。结构有一个用于每个成员的读取器，映射有一个用于键（字符串或数字）的嵌套读取器和另一个用于值的读取器。像列表在映射中，映射在结构中，结构在列表中这样的组合经常出现。

Logical Steps in Scanning a Table

Presto工作节点接收到要扫描的条带（stripe）。它查看行组元数据以确定是否可以基于元数据排除行组，实际上通常是列的最小/最大值。由于数据很少排序或以其他方式相关联，因此跳过整个行组是罕见的。

Presto表扫描然后定位到行组的开头。

扫描涉及多个列。对于每个列，我们要么评估一个过滤器并产生过滤器为真的行号集合，要么检索合格集中每行的值。我们也可以做两者，这种情况下，过滤器首先进行。如果列具有结构，即是一个列表、映射或结构，可能有子字段上的过滤器，并且只有查询引用的子字段的一部分。子字段是结构的成员，列表中的特定索引，映射中的特定键，或者可能指的是列表或映射中的元素数量。

起初，我们有过滤器的选择。有些过滤器可能与任何列无关，例如在随机抽样的情况下。如果我们有这样，这些将产生要扫描的初始行集。否则，初始集是行组的一部分。这个分数的大小取决于数据的宽度和目标批处理大小。因此，我们有一个初始的行选择集。这称为合格集，并且随着我们评估过滤器将被限制。

不同类型的过滤器

在实践中，大多数过滤器是单个列和文字之间的比较。文字可以是单个值、一组范围或IN列表。大多数时间过滤器是AND在一起的。每个顶级AND的项称为顶级连接词。大多数连接词是列和文字的比较。这些在它们自己的类别中可以独立评估，当解码列的表示时。在Presto上下文中，我们称这些为元组域过滤器。下一个最常见的过滤器是对列的表达式，例如对列进行正则表达式匹配或JSON字段提取。最后，有些情况是依赖于多列的表达式，例如discount > 0.08 OR comment LIKE ‘%special price%’。OR的两个操作数（析取项）可能合理地在列本身上进行评估，但是OR使这成为一个两列表达式。一个更常见的多列过滤器的例子是哈希连接探针下推到扫描中，带有多部分键。我们将在后面回到这一点。

过滤器和列顺序

SQL没有指定评估过滤器的顺序。所有连接词都为真的行是选择的结果。大多数过滤器都定义在一列的所有值上；因此，错误很少见。然而，有些过滤器可能会产生错误，例如除以零，在这些情况下，不同的过滤器顺序可能有不同的错误行为。

Presto在初始状态下按原始查询的顺序从左到右评估复杂过滤器，并发出第一行出现错误的最左边的错误信号。我们将其更改为根据它们的性能重新排序过滤器，并在没有假过滤器的第一行上发出第一个错误信号。

有了这个定义，我们现在可以完全自由地重新排列过滤器，以便我们尽可能早地获得最多的选择。过滤器的成本函数是time / (rows_in / rows_out)。值越低，过滤器越好。因此，我们可以按这个分数对所有过滤器进行排序，并且由于我们可以独立地并且以任意顺序读取列，我们可以根据过滤器的顺序重新排列列的顺序。唯一的限制是多列过滤器不能早于其最后一个操作数放置。

理论上解决这个排序问题的完整解决方案将类似于查询连接顺序选择，我们对所有可能的排列运行成本模型。在实践中，一些更简单的东西同样有效，例如首先按成本升序放置所有单列过滤器，然后在依赖此列的最后一个列之后放置所有多列过滤器，从最便宜的开始。如果过滤器依赖的列还没有放置在集合中，就添加它。放置完所有过滤器后，我们首先放置所有未过滤的列，最宽的列先放。

嵌套结构：列表、映射和结构

扫描结构就像扫描一组顶级列。结构内列不能仅仅被视为常规顶级列的原因是它们都共享一个结构级别的空指示器。在结构内，与顶级列之间完全相同的过滤器顺序选择是可能的。因此，读取结构首先从结构级别的行号合格集开始。这被转换为结构成员级别的行号集合。如果没有空结构，这种转换就是恒等的。内部合格集然后通过结构列上的过滤器进行限制。最后，这被转换为外层级别的合格行集。如果结果中包括了空结构，那么空值在其他所有内容之后添加。如果除了结构成员上的is null之外没有其他过滤器，那么只有在这种情况下才会发生最后一步。

列表或映射类似于结构，但现在每个顶层行可能有零个或多个嵌套行。现在内部合格集是顶层行到相应嵌套行号集合的双向映射，反之亦然。

过滤列表或映射增加了在一列的不同位置上应用不同过滤器的额外复杂性。考虑features[1] = 2 AND features[3] = 4的情况。这实际上是一个非常常见的情况，特别是在机器学习应用中，训练数据经常表示为映射。

这里的映射读取器读取键，并过滤掉值是1或3的位置。从这里，读取器知道哪些值位置应该有= 2和= 4作为过滤器。值列读取器的合格集设置为这些行，并创建了一个位置依赖的过滤器，以便我们交替应用一个或另一个条件。如果对于任何包含的行，我们少于2次过滤器命中，该行将被丢弃。如果对于任何包含的行，我们放置了少于2个过滤器，那么键就缺失了，这要么是一个错误，要么丢弃该行。一个全局配置控制了[]的错误行为。element_at(map, key)形式对于缺失的键始终是null。

根据是否投影出所有或部分映射键，还有一些更多的复杂性，但一般原则如上所述。列表类似于映射，只是在这里我们不需要键列来映射顶层行号和下标到值列中的位置。

Facebook的DWRF格式，一个定制的ORC V1，有一个称为flat map的额外概念。这有一个值列和每个不同键的呈现标志。当读取子集的键时，这比直接映射更有效率，至少需要跳过不想要的值。这个读取器变成了一个修改过的结构读取器。这也重新引入了过滤器重排序的可能性，也适用于映射。

最后，还有一些深度嵌套的映射、列表和结构的情况。表达式如map[1].field.list[0] = 10 AND map[2].field2.list2[1] = 11涉及一系列位置依赖的过滤器。这些操作是可组合的，并且通过简单地堆叠多层内部到外部的行号，按预期工作。在所有情况下，我们都需要在叶列上进行长紧循环，并且不需要一次处理一个元组。

适应性

到目前为止，我们有两种适应性：过滤器顺序和批量大小。过滤器顺序的目的是显而易见的：在好的情况下，它不需要任何成本，在坏的情况下它可以节省大量成本。它这样做不依赖于优化器成本模型，这是一个额外的优点。统计数据通常缺失或错误，无论如何，这些不包括数据相关性。这在DBMS中不是太大的问题，它写入了其所有数据，但在数据湖中，多个引擎在同一数据上工作，并且没有对元数据的集中控制，这是一个更大的问题。

适应批量大小是在对一个列的连续值进行长循环和保持中间结果的内存上限之间的折衷。列式数据表示的基本点是，压缩和循环一个列的连续值是高效的：相同的操作适用于所有，并且值都是同一域的。在同一个列上停留的时间越长，花在解释查询上的时间就越少，例如在列之间切换。

但是，随着数据通常是宽的、总是非规范化的，并且有不可预测的重复元素序列，例如对一个列的1K个值进行操作，然后移动到下一列，这不再实用。

在实践中，我们总是在内存压力下运行，基本上所有与Presto相关的可靠性事件都与内存耗尽有关。因此，我们必须在扫描表时强制执行内存上限。

这是通过保持过滤器选择性和列宽度的统计数据来完成的。基本公式是从一个提议的批量大小开始，对于每个列，添加值大小乘以应用在该列之前的过滤器的选择性的乘积。这给出了批量的估计大小。需要应用合理的安全边际，因为数据不是均匀分布的。通过这种方式，我们得到了一个估计，允许调整批量大小，以便我们有可能适应预算。如果超过了硬性限制，我们将使用更小的批量大小重新扫描。

这相对容易实现，并且只要重试发生在不到1/1000的行组中，我们就没问题。

在实践中，为了从对列的紧循环中获得收益，只要我们在最高基数列的几个千个值上循环就足够了。通常这是最嵌套的列。如果有这样的嵌套模式，处理的顶层行数在批量中并不是很重要。

Reference

https://prestodb.io/blog/2019/06/29/everything-you-always-wanted-to-do-in-table-scan/