HackerPapers

arXiv:1404.0703cs.DB

Joins via Geometric Resolutions: Worst-case and Beyond

Mahmoud Abo Khamis, Hung Q. Ngo, Christopher Ré, Atri Rudra

Abstract

We present a simple geometric framework for the relational join. Using this framework, we design an algorithm that achieves the fractional hypertree-width bound, which generalizes classical and recent worst-case algorithmic results on computing joins. In addition, we use our framework and the same algorithm to show a series of what are colloquially known as beyond worst-case results. The framework allows us to prove results for data stored in Btrees, multidimensional data structures, and even multiple indices per table. A key idea in our framework is formalizing the inference one does with an index as a type of geometric resolution; transforming the algorithmic problem of computing joins to a geometric problem. Our notion of geometric resolution can be viewed as a geometric analog of logical resolution. In addition to the geometry and logic connections, our algorithm can also be thought of as backtracking search with memoization.

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

On Hacker News

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

Comments linking this paper, per year.

Discussed in comments5 threads

  1. Why Hypergraphs? (2013) 1 comment

    • Funnily enough, this hypergraph view is used to describe symptomatic query complexity for cyclical joins, the simplest if which is "count triangles in adjacency list" (naive RDBMS yields O(n²) on pathological data, despite the wrist case optimal tactic being something like O(n +…

      namibjView 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. SpaceCurve: A Unique and Fast Geospatial Database 1 comment

    • Frustratingly light on detail, but the possible connections to http://arxiv.org/abs/1404.0703 are intriguing.

      jamiiView on HNParent context

  5. 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.