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

Skew Strikes Back: New Developments in the Theory of Join Algorithms

Hung Q. Ngo, Christopher Re, Atri Rudra · 2013
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2015-01-24 · 最近 2022-07-28
2不同的人
4活跃月份
4讨论串
25被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Evaluating the relational join is one of the central algorithmic and most well-studied problems in database systems. A staggering number of variants have been considered including Block-Nested loop join, Hash-Join, Grace, Sort-merge for discussions of more modern issues). Commercial database engines use finely tuned join heuristics that take into account a wide variety of factors including the selectivity of various predicates, memory, IO, etc. In spite of this study of join queries, the textbook description of join processing is suboptimal. This survey describes recent results on join algorithms that have provable worst-case optimality runtime guarantees. We survey recent work and provide a simpler and unified description of these algorithms that we hope is useful for theory-minded readers, algorithm designers, and systems implementors.

候选层:至少 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原评论 ↗
评论j-pb · 2019-12

“Out of the examples I would take a look at the LogicBlox Stuff, they gave join algorithm research a big push with their Leapfrog-Triejoin. The following papers ascend in difficulty, and are based on each other, but offer a fascinating glimpse into the connection of DPLL SAT solving and Conjunctive Query evaluation. https://openproceedings.org/2014/conf/…”

Ask HN: Why GraphQL APIs but no Datalog APIs?原评论 ↗
评论j-pb · 2021-01

“It's all about efficient range reads and seek operations. You can compute set operations pretty efficiently using sorted indices that support a "find next or greater" operation. For intersection, take the first value from the first set as the smallest candidate of the output set, then call call candidate:= next(candidate) on each set, updating the candi…”

Ordered Key-Value Stores原评论 ↗
评论j-pb · 2022-07

“That blogpost is a godsend, it provides a great explanation and intuition, and resolved a few questions that I was left with after reading a lot of WCO join papers. Good nitpick, I think you can construct larger rings where the difference becomes larger than one, but I might be wrong. The dynamic variable ordering trick makes a huge difference in practic…”

SQLite Internals: Pages and B-trees原评论 ↗