HackerPapers

arXiv:1310.3314cs.DB

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

Hung Q. Ngo, Christopher Re, Atri Rudra

Abstract

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.

arXiv comments
Journal reference
DOI
Subjects
cs.DBDatabases cs.DSData Structures and Algorithms

On Hacker News

Linked by 2 identifiable commenters in 4 comments across 4 threads, from Jan 2015 to Jul 2022.

Comments linking this paper, per year.

Discussed in comments4 threads

  1. SQLite Internals: Pages and B-trees 1 comment

    • 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…

      j-pbView on HNParent context

  2. Ordered Key-Value Stores 1 comment

    • 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…

      j-pbView on HNParent context

  3. Ask HN: Why GraphQL APIs but no Datalog APIs? 1 comment

    • 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…

      j-pbView on HNParent context

  4. Architecture of a Database System 1 comment

    • 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…

      jamiiView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.