按年被提到
20122015 · 1 次2026
系统、数据库与网络›数据库与向量检索·arXiv:1210.0481 · cs.DB

Leapfrog Triejoin: a worst-case optimal join algorithm

Todd L. Veldhuizen · 2012
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2015-01-24 · 最近 2020-02-01
2不同的人
2活跃月份
2讨论串
46被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Recent years have seen exciting developments in join algorithms. In 2008, Atserias, Grohe and Marx (henceforth AGM) proved a tight bound on the maximum result size of a full conjunctive query, given constraints on the input relation sizes. In 2012, Ngo, Porat, R{é} and Rudra (henceforth NPRR) devised a join algorithm with worst-case running time proportional to the AGM bound. Our commercial Datalog system LogicBlox employs a novel join algorithm, \emph{leapfrog triejoin}, which compared conspicuously well to the NPRR algorithm in preliminary benchmarks. This spurred us to analyze the complexity of leapfrog triejoin. In this paper we establish that leapfrog triejoin is also worst-case optimal, up to a log factor, in the sense of NPRR. We improve on the results of NPRR by proving that leapfrog triejoin achieves worst-case optimality for finer-grained classes of database instances, such as those defined by constraints on projection cardinalities. We show that NPRR is \emph{not} worst-case optimal for such classes, giving a counterexample where leapfrog triejoin runs in $O(n \log n)$ time, compared to $Θ(n^{1.375})$ time for NPRR. On a practical note, leapfrog triejoin can be implemented using conventional data structures such as B-trees, and extends naturally to $\exists_1$ queries. We believe our algorithm offers a useful addition to the existing toolbox of join algorithms, being easy to absorb, simple to implement, and having a concise optimality proof.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论jamii · 2015-01

“Some of the more exciting ideas I've seen recently: http://arxiv.org/abs/1310.3314 - Understanding the core difficulty in answering relational queries and examples of problems for which current query optimisers always produce plans which are asymptotically suboptimal http://arxiv.org/abs/1404.0703 - The first theoretical analysis which can relate the ch…”

Architecture of a Database System原评论 ↗
被提交为 story · 1 次