Velox: Meta’s Unified Execution Engine

本文为摘录(或转载)，侵删，原文为： 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

5.5.1 Table Scans, Filter, and Project

5.5.2 Aggregate and Hash Joins.

5.6 Memory Management

5.6.1 Caching