系统与数据库2021arxiv.org
PathQuery：Google 的图查询语言
PathQuery, Google's Graph Query Language
进阶 · 约 60 分钟读完前置知识：图数据库基础、知识图谱概念、SPARQL 或类似查询语言经验
导读
这篇论文介绍了 PathQuery，Google 内部用于查询其知识图谱（Knowledge Graph）的图查询语言。论文阐述了该语言的语法、数据类型、图匹配与聚合等核心设计，展示了它如何在大规模图数据上高效运行。
HN 关注点：HN 读者对 Google 内部大规模图查询系统的实现细节很感兴趣，讨论焦点集中在 PathQuery 与 SPARQL、Datalog、GROQ 等其他查询语言的对比与设计取舍。
HN 评论精选
这几条评论里：质疑 2 补充 1 亲历 1
亲历亲历者称赞 Google 知识图谱的扩展性与查询性能，并认为论文写得清晰易读。
2013 年我曾受邀参与 Google 一个使用知识图谱的内部项目。当时我刚写了两本关于 RDF/SPARQL/关联数据的书，起初对他们使用的查询语言感到不适应，但当我意识到知识图谱的扩展性和查询速度有多好之后，我成了它的粉丝。另外，这篇论文写得非常好——图查询并不容易讲清楚，但他们的示例和文字让数据类型、语法、匹配和聚合都很容易理解。
mark_l_watson查看英文原文
I was invited to work at Google in 2013 on an internal project using their Knowledge Graph. I had just written two books on RDF/SPARQL/linked-data and at first I was taken aback by the query language used at the time. However, when I realized how well the KG scaled and how fast the queries were, I became a fan. BTW, I think this paper is very well written. Graph queries is not an easy topic and their examples and text make the data types, syntax, and how to perform matches and aggregations easy to follow.
补充GROQ 开发者指出 PathQuery 与 GROQ 结构相似，并分享规范与实现。
PathQuery 看起来很像 Sanity 数据存储使用的查询语言 GROQ。论文中的一个查询示例可以用 GROQ 类似地表达。PathQuery 当然复杂得多，但基本结构非常相似。GROQ 目前还缺少遍历图所需的递归查询能力，但这已在我们的实现路线图上。我们已发布 GROQ 的公开草案规范，希望更多工具采用，并已有开源的 JavaScript 实现。（利益披露：我在 Sanity 参与 GROQ 开发。）
atombender查看英文原文
PathQuery looks a lot like GROQ [1], which is the query language used by the Sanity data store [2]. For example, one of the queries in the paper: @entities .[/type == (Id(/ museum ) , Id(/ theme_park ))] .{ id: ?cur require name: /name.[TextLang() == en ] @merge : events::GetInfo() } can be written something like: *[type == "museum" || type == "theme_park"] { id, name: select(name[lang == "en"] => name), ...{ // GROQ doesn't have functions, so GetInfo() // would need to be inlined here } } PathQuery is of course a lot more complex, but the basic structure seems very similar. One thing GROQ does not have yet is recursive querying of the type needed to traverse graphs, but this is on our roadmap to implement. We've published a public draft specification for GROQ, and hoping it will be adopted by more tools. For example, we already have an open-source JavaScript implementation of it. (Disclosure: I work on GROQ at Sanity.) [1] https://github.com/sanity-io/GROQ [2] https://www.sanity.io/
质疑质疑论文未提及 Datalog，并用 Datomic 示例展示多语言查询的写法及索引设计思考。
奇怪的是论文没有提到用 Datalog 做图遍历。在 Datomic 或 Datascript 风格的 Datalog 中，支持多语言名称的查询可以这样写……可以把 locale 存在名字字符串里，但那样就无法高效过滤。只有 4 元组 EAVT 索引时，要查询复合值（如 ["Hello" "en"]）的组件就需要中间 join，所以我一直在尝试做自己的图数据库，用 5 元组或更多可扩展索引（如 EAXVT，X 表示 locale），但那样索引顺序就很重要了。
pgt查看英文原文
Curious that there is no mention of Datalog [^1] for graph traversal in the paper. To support multi-locale names in Datomic or Datascript-flavoured Datalog attractions_v1.pq would be written as (where :entity/locale is of type :db.type/ref): (d/q [:find ?id ?name ?lang :in $ ?type :where [?e :entity/type ?type] [?e :entity/locale ?loc] [?loc :locale/name ?name] [?loc :locale/lang ?lang] db #{"museum" "theme_park"}) => (["/z/38dwfnb8" "Museum of Modern Art" "en"] ["/z/38dwfnb8" "Museo de Arte Moderno" "es"] ...) You could store the locale inside the name string, but then you can't efficiently filter on it. If you want the whole shebang, can do `(pull ?id [*])`. It's not obvious in their example if the locale filtering is post-query or part of the unification. With only 4-tuple EAVT-style indices, you need an intermediate join to support compound values like ["Hello" "en"] if you want to query against the components, so I have been toying with making my own graph DB with 5-tuple (or more) extensible indices, e.g. EAXVT, where X would be the locale, but then index order matters. [^1]: http://www.learndatalogtoday.org/
质疑质疑论文称 SPARQL 不够“图化”的说法，指出其忽略了 SPARQL CONSTRUCT。
有人能解释一下为什么他们没有提到 SPARQL 的 CONSTRUCT 语句吗？我很难接受他们关于 SPARQL 不够“图”的说法。不过也可能是我漏掉了什么。
netfl0查看英文原文
Can someone explain why they did not mention SPARQL CONSTRUCT statements? I struggle with the notion that SPARQL isn’t “graphy” per their assertion. I may be missing something though. https://www.w3.org/TR/sparql11-query/#construct
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2021Hacker News 讨论帖172 分 · 47 评
同领域还值得读
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 分钟编辑精选