Velox: Meta’s Unified Execution Engine

2022-10-01 约 1915 字预计阅读 4 分钟

Table of Contents

1 ABSTRACT
2 INTRODUCTION
3 LIBRARY OVERVIEW
4 USE CASES
5 DEEP DIVE
- 5.1 TODO Type System
- 5.2 Vectors
- 5.3 Expression Eval
- 5.4 Functions
- 5.5 Operators
- 5.6 Memory Management

本文为摘录(或转载)，侵删，原文为： attachments/pdf/8/p3372-pedreira.pdf

1 ABSTRACT

Velox:

C++ database acceleration library
用来：
- 构建执行引擎
  - 应对复杂数据类型
- 增强数据管理系统 (enhance data management system)
倚赖：
- 向量化 (vectorization)
- 自适应 (adaptivity)
Meta 内部已经或正在将其与其他组件集成，包括：
- 分析型查询引擎
  - Presto
  - Spark
- 流处理平台
- 消息总线
- 数据仓库
- 机器学习
  - PyTorch

2 INTRODUCTION

仅做计算，无 SQL 解析、优化器等，其价值：

效率
一致性
工程效率

3 LIBRARY OVERVIEW

是什么
- 开源 C++ 数据库加速库
- 可用来加速、扩展和增强数据的计算引擎：
  - 高性能计算
  - 可重用
  - 可扩展
不是什么
- 无语法前端
  - SQL 解析
  - 全局优化等
也就意味着：
- Velox 的输入是 已经优化好的执行计划
- 将执行计划在本地执行

Velox 的组件

4 USE CASES

5 DEEP DIVE

TODO 5.1 Type System

TypeSystem 用于表示各种数据类型：
- 原生类型
  - 整形
  - 不同精度的浮点数类型
  - 字符串
    - varchar
    - varbinary
  - 日期
  - 时间戳
  - 函数（lambda 表达式）
- 复杂类型
  - 数组
  - 固定长度的数组
  - maps
  - rows, structs
上述类型可以嵌套，并序列化、反序列化
- 还可以包装 C++ 的结构体
支持类型扩展：
- Find How????

5.2 Vectors

Vectors 用来表示列式数据
- 列式、编码后的数据
- 用作组件之间的输入和输出
- 扩展自 Apache Arrow 格式，扩展包括
  - size （行数）
  - type
  - null bitmap
- 可嵌套

Velox Buffers
- 从内存池中分配出的连续空间
- Vector 保存在 Velox buffers 中
引用计数
- Buffer 和 Vector 都有引用计数
- 一个 buffer 可以被多个 Vector 引用
- 只有引用计数为 1 的数据是可变的
  - shared vector 和 buffer 可通用 copy-on-write 技术变成可写

5.2.1 Arrow Comparison

5.3 Expression Eval

表达式计算引擎，可用作
- 过滤投影算子 – 用于过滤和投影表达式
- TableScan 和 IO connectors: 过滤条件下推
- 用作单独的计算组件：计算表达式
使用 Expression Tree 用作输入
- 树的每个节点可能是
  - input column
  - 常量
  - 函数调用，由函数名和一系列的参数（表达式）构成
  - CAST 表达式：用于类型转换？
  - lambda 函数
函数计算分成两个部分：编译和执行

5.3.1 Compilation

将输入的表达式树转换成为可执行的表达式，若干运行时优化技术：

Common Subexpression Elimination
Constant Folding
Adaptive Conjunct Reordering

5.3.2 Evaluation.

5.4 Functions

5.4.1 Scalar Functions.

5.4.2 Aggregate Functions

5.5 Operators

Velox 计划由 PlanNodes 组成，执行时候，计划树被翻译成为执行树（ExecTree）。多数情况下，计划节点到执行节点（执行器）是一一对应的，只有少数例外，如：

Filter + Project ==> FilterProjector
HashJoin ==> HashBuild + HashProbe

最顶层的Velox执行概念是任务（Task），它是分布式执行中功能传递的单位，对应于查询计划片段及其运算符树。任务以表扫描（TableScan）或交换（Exchange，洗牌）源作为输入开始，并以另一个交换作为结束。任务的运算符树被分解为一个或多个称为管道（Pipelines）的线性子树：例如，HashProbe和HashBuild分别映射到一个管道。每个管道有一个或多个执行线程，称为驱动程序（Drivers），每个驱动程序都有其自己的状态。驱动程序可以在线程上运行或不运行，具体取决于它们是否有工作要执行。驱动程序可能因多种原因离开线程，例如，其消费者尚未消耗数据，源交换尚未产生数据，或扫描正在等待扫描文件。与传统的火山迭代器树模型相比，这种模型在进出线程时更加便利，因为状态可以恢复，而无需在栈上构建控制流。

最后，任务可以随时被其他Velox参与者取消或暂停。在强制优先级、检查点状态、迫使其他任务溢出或其他协调活动的情况下，能够暂停任务是非常方便的。

所有运算符都实现了相同的基本API，包括诸如添加一批向量作为输入、获取一批向量作为输出、检查运算符是否准备好接受更多输入数据，以及通知不再添加更多数据等方法；后者可以用来通知阻塞排序或聚合以刷新其内部状态并开始生成输出。尽管Velox已经提供了一整套常用的运算符，但该库也允许引擎开发人员添加包含特定于引擎的业务逻辑的自定义运算符，例如用于流处理的基于流的聚合。一些常见运算符的重要特性和优化将在接下来的小节中描述。

5.5.1 Table Scans, Filter, and Project

表扫描是按列逐个进行，并支持过滤下推。

包含过滤器的列会首先被处理，生成命中行号以及可选的命中值。过滤器在运行时根据适应性进行排序，以确保优先评估在最短时间内能够丢弃值的过滤器。评分的定义为 时间 / (1 + 输入值 - 输出值) ，使得最佳过滤器在最短时间内丢弃最多的值。这与在AND/OR表达式中重新排序合取子句的原则相同，如第4.3节所述。

简单过滤器使用SIMD一次评估多个值，从而使Velox能够利用AVX2每个CPU时钟周期大致处理一个整数命中。字典编码数据的过滤结果会被缓存（如第4.3节所述），而SIMD再次用于通过 聚合 + 比较 + 掩码查找 + 重新排列 来检查缓存命中，从而平均在每个CPU时钟周期内处理多个命中并输出符合条件的行。Velox还提供了针对大IN 过滤器的高效实现，用于哈希连接下推，允许同时触发4次缓存未命中。

此外，FilterProject运算符为所有的过滤和投影表达式使用一个单一的表达式评估上下文。对于每一批输入数据，运算符首先在所有输入行上评估过滤表达式，仅在通过过滤的行子集上执行投影表达式。如果没有行通过过滤，则完全跳过投影表达式的评估。

目录