系统与数据库2018cs.purdue.edu编辑精选
如何架构查询编译器：再探
How to Architect a Query Compiler, Revisited
进阶 · 约 60 分钟读完前置知识：数据库查询执行、编译原理基础、函数式编程/DSL
导读
这篇 SIGMOD 2018 论文回顾了如何架构一个查询编译器：将查询计划编译为高效的原生代码，重点对比了迭代器（pull）模型与以数据为中心（push）模型的执行方式，指出后者能显著提升查询执行性能。作者 Tiark Rompf 团队延续其多阶段编程/代码生成（LMS）的研究路线。
HN 关注点：数据库查询编译与代码生成技术，尤其是它与 Spark 等大数据系统性能问题的关联，作者本人也在评论区参与讨论。
HN 评论精选
这几条评论里：支持 1 补充 1 亲历 1
补充推荐 Rompf 团队的一系列相关论文和演讲作为背景阅读
很高兴看到 Tiark Rompf 团队的论文。这里还有一些他们的其他优秀工作：Lightweight Modular Staging（运行时代码生成与编译型 DSL 的实用方法）、Collapsing Towers of Interpreters、LMS-Verify 等，Nada Amin 关于后两篇的演讲也非常精彩。另外还有我最喜欢的一篇：用 500 行代码写一个 SQL 到 C 的编译器。都是些令人震撼的工作。
rwhaling查看英文原文
It's always nice to see the papers that come out of Tiark Rompf's group. For background, here are some other great ones: Lightweight Modular Staging: A Pragmatic Approach to Runtime Code Generation and Compiled DSLs https://infoscience.epfl.ch/record/150347/files/gpce63-rompf.pdf Collapsing Towers of Interpreters: https://www.cs.purdue.edu/homes/rompf/papers/amin-popl18.pdf LMS-Verify: Abstraction Without Regret for Verified Systems Programming: http://lampwww.epfl.ch/~amin/pub/lms-verify.pdf There's a ton more. Nada Amin's talks on the last two papers are excellent also: https://www.youtube.com/watch?v=QuJ-cEvH_oI https://www.youtube.com/watch?v=Ywy_eSzCLi8 Oh, and I forgot my favorite: Functional Pearl: A SQL to C Compiler in 500 Lines of Code https://www.cs.purdue.edu/homes/rompf/papers/rompf-icfp15.pdf Some really mind-blowing stuff.
亲历作者现身答疑，并介绍基于同样技术的 Spark 加速项目 Flare
大家好，我是作者，很高兴看到论文登上首页，欢迎提问！既然评论里提到了 Spark，可以看看我们后续用类似技术加速 Spark 的工作：Flare（将发表于 OSDI）。如果你在生产环境用 Spark 并想试用，欢迎留下联系方式，我们团队很小、等待名单较长，但今年秋季的私有测试还有一些名额。
tiarkrompf查看英文原文
Hi all, Author here, great to see our paper on the front page today. Happy to answer any questions! Since Spark was already mentioned in the comments, you might be interesting in the parallel/follow-on work we did applying similar techniques to accelerate Spark: "Flare: Optimizing Apache Spark for Scale-Up Architectures and Medium-Size Data" (to appear at OSDI, preprint here: https://www.cs.purdue.edu/homes/rompf/papers/essertel-osdi18.pdf) If you're running Spark in production and are interested in trying it out, please leave your contact data here: https://flaredata.github.io. We're a small team and have a long waitlist, but should have some open slots in our private beta program this Fall. Cheers, - Tiark
支持解释 pull 与 push 模型的性能差异，并指出 Spark 新版已转向编译器方案
很高兴看到论文专门对比了迭代器（pull）模型与数据为中心（push）模型，这正是我在 Apache Spark 的 RDD 中看到的问题。想象一个常见流水线：输入数据→处理→输出。用迭代器时，输出逻辑通过处理逻辑提供的抽象 next() 接口循环，处理逻辑又依赖输入逻辑的 next() 接口，依赖链一长，CPU 缓存就被彻底破坏。如果用手写常规编程语言，我们绝不会用这种倒置的模型，而是直接输入、处理、输出——这正是论文提出的做法：在查询求值的关键阶段提供回调函数，用编译器加速查询执行。值得一提的是 Spark 维护者也意识到迭代器性能差，新版本 Spark 已采用编译器方式。
chrisaycock查看英文原文
I'm glad to see the paper specifically contrast iterator approaches (pull model) versus a "data-centric" approach (push model). This was indeed the issue I've seen with Apache Spark's RDD. Imagine a common pipeline: - input data - process data - output data Using iterators, the output logic loops over an abstract next() interface provided by the process logic, which in turn loops over another abstract next() interface provided by the input logic. Given a long enough chain of dependent processes, the CPU's cache will be obliterated. If we were to write code in a regular programming language by hand, we would never use such an inverted model. Instead, we would directly input the data, process it, and then output it. That's exactly what the paper proposes; the authors supply a callback function at the major stages of query evaluation. They use this model in the context of writing a compiler to speed query execution. It's worth noting that the Spark maintainers also realized that iterators have bad performance and that newer versions of Spark follow the compiler approach: https://databricks.com/blog/2016/05/23/apache-spark-as-a-compiler-joining-a-billion-rows-per-second-on-a-laptop.html
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2018Hacker News 讨论帖212 分 · 9 评
同领域还值得读
I/O 比 CPU 更快——让我们划分资源并消除操作系统抽象
I/O Is Faster Than CPU – Let’s Partition Resources and Eliminate OS Abstractions
指出在现代服务器硬件上 I/O 速度已接近甚至超过 CPU，传统操作系统抽象反而成为瓶颈。
系统与数据库2019 · 817 分 · 277 评进阶 · 约 30 分钟编辑精选使用 io_uring 的高效 I/O
Efficient IO with io_uring
由 Linux 内核开发者 Jens Axboe 撰写，介绍 Linux 新的异步 I/O 接口 io_uring。
系统与数据库2019 · 426 分 · 96 评进阶 · 约 45 分钟编辑精选线程对大多数用途而言是个坏主意（1995）
Threads Are a Bad Idea for Most Purposes (1995)
这篇 1995 年的文章由 John Ousterhout 撰写，讨论为什么线程对大多数用途而言是坏主意，并主张事件驱动编程通常更简单、更高效。
系统与数据库2017 · 423 分 · 382 评进阶 · 约 25 分钟编辑精选学习型索引结构之论证
The Case for Learned Index Structures
提出把索引看作一种"模型"：既然 B-tree 等结构本质上是在学习数据的分布，就可以用机器学习模型（如回归模型、神经网络）来近似键到位置的映射，从而替代 B-tree、哈希索引…
系统与数据库2017 · 398 分 · 66 评 · 引用 25进阶 · 约 60 分钟编辑精选FoundationDB：一个分布式、解耦的事务型键值存储
FoundationDB: A distributed, unbundled, transactional key value store
介绍 FoundationDB：一个分布式、解耦设计的事务性键值存储。
系统与数据库2021 · 283 分 · 99 评进阶 · 约 90 分钟编辑精选