Queryparser，一款开源 SQL 解析工具

在 2015 年初，Uber 开始将业务迁移到多个活跃的数据中心。作为初步迁移活动的一部分，Uber 工程部门将其业务实体的 ID 从整数类型转变为 UUID 类型。为了实现这点，我们的数据仓库团队被分配了一个任务——明确数据仓库中每个表之间的每个外键关联，从而用相应的 UUID 回填所有的 ID 列。（剧透警告：最终会有几十个主键需要迁移。每个主键可能有许多外键，而且这些外键会有许多不同的别称。最坏情况下的外键有超过 50 个不同的别称。）

考虑到我们数据表的分散性，这不是一件简单的事。最有希望的方案是，从所有提交到数据仓库的 SQL 查询中提取外键关联信息，然后观察哪些列关联在一起。为了服务这个需求，我们构建了一款开源 SQL 解析工具—— Queryparser 。

在本文中，我们会讨论 Queryparser 的实现、它开启的应用多样性以及发展过程中所遇到的一些问题和限制。

实现

在 Uber 内部，Queryparser 采用流式架构部署，如图 1 所示：

图 1:Uber 的流式架构数据仓库通过 Queryparser 处理所有的查询。方框表示服务，管道表示数据流。目录信息（catalog info）服务负责跟踪数据仓库中的数据表的 schemas。

Queryparser 分析每一个提交到数据仓库的实时查询，然后将分析结果发送到另外一个单独的流中。单个查询的处理步骤分为三步，如图 2 所示。
步骤 1: 解析 将一个原始字符串转换为一个 AST（abstract syntax tree，抽象语法树）表达式。
步骤 2: 处理 遍历原始的 AST，然后应用范围规则。在列名前增加表名，然后在表名前增加 schema 名。需要输入每个表的所有列名和每个 schema 中的所有表，也就是所谓的“目录信息”。
步骤 3: 分析 遍历处理过的 AST，寻找那些进行相等比较的列。

图 2:Queryparser 分三步来处理一个查询：解析、处理和分析。上面的流程图通过数据类型的转换，从概念上展示了这个处理流程。下面的流程图通过一个真实的查询完整展示了这个流程。

Queryparser 的实现和架构成功地确定了外键关联关系——考虑到这个原型只覆盖了部分 SQL 语法，目录信息完全是硬编码的，而且我们对于什么算作一个外键关联一直在演变，这真的是非常棒的结果。（外键关联包括明显的“SELECT * FROM foo JOIN bar ON foo.a = bar.b”，到不太明显的 “SELECT * FROM foo WHERE foo.a IN (SELECT b from bar)” ，到值得商榷的“SELECT a FROM foo UNION SELECT b FROM bar”。我们在确定关联关系时会尽可能地宽泛一些，因为无论如何结果都会被人工检查的。）

选择 Haskell

在开源的 Queryparser 代码库中，你可能已经注意到一件事，它是用 Haskell 编写的。Queryparser 最初是由一名热衷 Haskell 的 Uber 工程师创建的，然后迅速获得了其他一些工程师的支持。事实上，为了开发它，我们中的很多人特意学了 Haskell。

从结果来看，用 Haskell 来搭建 Queryparser 原型是一个不错的选择。这有许多方面的原因。首先，Haskell 有非常成熟的语言解析支持库。它的表达式类型系统对于我们内部的 SQL 查询模型的频繁重构和扩展非常有用。另外，我们重度依赖编译器来指导我们进行那些大得吓人的重构。如果使用动态类型语言来进行相同的尝试，可能会花费数周时间来折腾运行时 bug，而 Haskell 的编译器可以很快给我们标记出来这些 bug。

用 Haskell 编写 Queryparser 的主要缺点是没有足够的开发者懂 Haskell。为了向我们更多的工程师介绍 Haskell，我们启动了一个每周读书小组，小组成员在午饭后聚在一起讨论 Haskell 相关的书和文档。

考虑到与 Uber 其余的非 Haskell 的基础设施的互联互通，Queryparser 一直部署在一个 Python 代理服务器后面。你可以在本文的 _ 部署 Queryparser_ 章节了解更多细节。

各种各样的方案

经历了 Queryparser 的早期成功之后，我们考虑了使用其它方法来优化我们的数据仓库运维。除了实现关联检测，我们还决定实现其它一些分析功能：

表访问：查询中访问了哪些表
列访问：查询子句中访问了哪些列
表变更记录：查询修改了哪些表，哪些输入决定了它们的最终状态

总之，这些新的分析使我们对数据仓库的访问模式有了细致入微的理解，从而可以在以下方面取得进展：表管理、定向通知、数据流理解、事故响应以及防御性运维（defensive operations），概括如下：

表管理

关注表管理有三重好处。首先，表访问统计通过发现那些不经常访问的表，使我们释放那些表的存储空间和计算资源，然后删除它们。

其次，列访问统计通过优化表在硬盘上的分布，使我们提高数据库性能，特别是针对 Vertica 投影 (projections) 。其中的窍门是，将 GROUP BY 的首列设为分组主键，将 ORDER BY 的首列设为排序主键。

最后，列关联统计通过确定频繁关联的表，然后用一个维度建模（dimensionally modeled）的表来取代它们，使我们提高数据可用性并减少数据库负载。

定向通知

表访问统计，使我们可以向数据消费者发送定向通知。关于数据表结构的更新或者数据质量问题，我们不必向数据工程部门邮件列表中的所有人发送这些信息，而只向最近访问过相关表的数据消费者发送这些信息就可以了。

数据流理解

表世系数据（译注：指数据表从源数据开始，经过数据转换到最终的表数据的整个过程中的各种信息数据。）开启了一项特殊的用例：如果将一系列查询一起分析，就可以根据表世系数据汇总出整个序列的数据流图。

例如，下面图 3 中的假设 SQL，从表 B 和表 C 生成了一个重新建模的表（modeled table）A：

图 3: 根据 SQL 查询从表 B 和表 C 计算出重新建模的表 A 的步骤。

在下面的图 4 中，我们描述了 Queryparser 为序列中的每个查询生成的表变更记录。另外，我们还描述了序列中的每个查询的累积数据流。最后，累积数据流（正确地）记录了表 A 对表 B 和表 C 的依赖关系。

图 4: 图 3 中的 SQL、每个查询对应的表变更记录、累积数据流、累积数据流的解释。

我们修改 ETL 框架来记录每个 ETL 的 SQL 查询序列，然后将他们提交给 Queryparser，Queryparser 这时会通过程序生成我们数据仓库中所有重新建模的表的数据流图。请看下面图 5 的例子：

图 5: 一个数据流图示例，代表 4 个原始表（A、B、C、D）和 3 个重新建模的表（E、F、G）描绘了查询是如何被 Queryparser 处理的。事实上，原始表通常来自上游的运维系统，例如 Kafka topics、 Schemaless datastores 和面向服务架构（SOA，service-oriented architecture）的数据库表。重新建模的表存在于数据仓库（Hive）和下游的数据集市（Vertica）。

事故响应

表世系数据对于响应数据质量事故非常有用，通过明确事故影响可以减少修复时间。例如，考虑到图 5 中的表依赖关系，如果在原始表 A 中有一个问题，那么我们就会知道影响范围包括表 E 和表 G。我们同时也会知道，一旦这个问题解决了，表 E 和表 G 也需要进行回填。为了强调这一点，我们可以结合表世系数据和表访问数据，定向通知表 E 和表 G 的所有用户。

表世系数据对于明确事故根本原因也非常有用。例如，如果在图 5 中的重新建模的表 E 中有一个问题，那么它只可能是由原始的表 A 或表 B 引起的。如果在重新建模的表 G 中有一个问题，那么它可能是由原始的表 A、B、C 或者 D 引起的。

防御性运维

最后，在运行时分析查询的能力使得防御性运维成为可能，使我们的数据仓库能够运行得更加流畅。Queryparser 可以在半途中截获路由到数据仓库的查询，然后进行分析。如果 Queryparser 监测到解析错误或者特定的查询错误模式，就可以拒绝这些查询，从而减少数据仓库的整体负载。

问题和限制

Fred Brooks 说，软件工程没有银弹。Queryparser 也不例外。虽然它优化了我们的存储需求，但是也存在一些问题。随着项目的开源，显露出一些有趣的本质上的复杂性。

语言功能的长尾效应

首先，而且毫无疑问的是：当对一种新的SQL 方言增加支持时，实现不经常使用的语言功能有一种长尾效应，这需要显著改变一个查询的Queryparser 内部表达式。长尾效应在原型阶段就很明显，当Queryparser 专注于处理 Vertica 的时候，以及增加对 Hive 和 Presto 的支持的时候，长尾效应更加明显。例如，在 Vertica 中解析 TIMESERIES 和 OFFSET 需要向 SELECT 语言增加新的子句。另外，在 Hive 中解析 LEFT SEMI JOIN 需要一种新的拥有特殊范围规则的关联类型，而在 Presto 中（tables 从属于 schemas，schemas 从属于 databaes）解析“databases”的顶级命名空间需要大量重新解析访问结构。（对于 SQL“w.x.y.z”，哪个标识是列名？根据目录状态和所处上下文，可能是“w”表示列名，而“x.y.z”表示嵌套的结构体字段，也可能是“z”表示列名，而“w.x.y”表示“database.schema.table”，或者介乎这两者之间的某种表示。）

跟踪目录状态

第二，跟踪目录状态是很困难的。请记住，解决列名和表名问题离不开目录信息。Uber 的数据仓库支持高并发的工作负载，包括并发 schema 变更，传统的新建、删除和重命名表，以及从一个现有表中新增或删除列。我们使用 Queryparser 进行实验来跟踪目录状态；假设 Queryparser 已经在分析每个查询，那么我们会想，我们是否可以简单地增加一个 schema 变更分析报告，并结合原来的目录状态来推导出新的目录状态。最终，由于对整个查询流进行排序比较困难，因此这个方案不怎么成功。我们的备选（也是更高效的）方案将目录状态视为几乎静态的，通过配置文件跟踪 schema 的成员关系和表中的列，反而比较成功。

会话查询

第三，使用 Queryparser 进行会话查询是非常难的。在一个理想的世界中，Queryparser 能够跟踪表在整个数据库会话期间的变更信息，包括事务、回滚和各种级别的事务隔离。然而在现实中，从查询日志中重建数据库会话是很难的，因此我们决定不对那些功能增加表变更信息支持。相反，Queryparser 依靠 Uber 的 ETL 框架的支持来实现 ETL 会话查询。

渗透抽象

最后，Hive 是底层文件系统上的一种渗透抽象。例如，INSERTs 可以用多种方式实现：

1. INSERT INTO foo SELECT … FROM bar
2. ALTER TABLE foo ADD PARTITION … LOCATION ‘/hdfs/path/to/partition/in/bar’

Uber 的 ETL 框架最初使用第一种方法，但是当第二种方法展现出引人注目的性能提升之后，就迁移到了第二种方法。这导致了表世系数据相关的的问题，因为 Queryparser 不能够将’/hdfs/path/to/partition/in/bar’解释为相应的表 bar。通过使用正则表达式来从 HDFS 路径中推导出表名，临时解决了这个特殊问题。然而，在一般情况下，如果你选择绕过 Hive 的 SQL 抽象来支持文件系统层的操作，那么你就会放弃 Queryparser 分析。

部署 Queryparser

在 Uber 的非 Haskell 基础设施中部署一个 Haskell 服务可能需要一点创造力，但绝不是一个大问题。

安装 Haskell 本身是非常简单的。在 Uber 的标准基础设施模式中，每一个 Docker 容器中运行一个服务。容器层的依赖关系通过配置文件来管理，因此增加对 Haskell 的支持和在所需软件包列表中增加 Stack 一样简单。

Queryparser 内部部署为一个 Haskell 项目，运行在一个 Python 服务包装器后面，从而与 Uber 的其它基础设施互联互通。其中的 Python 包装器作为一个代理服务器，只是将请求转发到同一个 docker 容器上的 Haskell 后端服务器。Haskell 服务器由一个主线程组成，这个主线程监听 UNIX 域 socket 上的请求；当一个新请求到达时，这个主线程衍生出一个工作线程来处理这个请求。

Python 包装器还依靠 Haskell 后端来发送监测数据。监测数据通过另外一个 UNIX 域 socket 来传送，而数据从相反的方向流动：一个 Python 层的守护线程监听来自Haskell 层的监测数据。

为了共享Python 层与Haskell 层的配置，我们在Haskell 层实现了一个微型的配置解析器，它可以理解Uber 惯用的Python 分层配置文件。

最后，我们使用 Thrift 来定义服务接口。这是 Uber 的标准选择，而且由于 Thrift 支持 Haskell，因此 Haskell 服务器可以开箱即用。编写 Python 代码来透明地转发请求，需要深入二进制协议，这是最困难的运维步骤。

总结

Queryparser 开启了各种解决方案，但也有许多有趣的局限性。它从最初的一款简陋的迁移工具，变成一种洞悉大规模数据访问模式的媒介。

如果你对类似的项目工作感兴趣，可以发邮件到 za@uber.com 或者在Uber Careers 页面申请数据知识平台团队的职位来和我们一起工作。

查看英文原文： Queryparser, an Open Source Tool for Parsing and Analyzing SQL

感谢冬雨对本文的审校。