Graph Theory Approach to Worst Case Optimal Joins in Database Query Processing
By
eatonphil
Toasted golden, schmeared with insight. Top of the rack.
Summary
This article introduces the concept of Worst Case Optimal Joins through the lens of graph theory, using TPC-H Query 5 (Local Supplier Volume) as a case study. It explains how database join operations can be represented as hypergraphs where nodes represent join variables and edges represent relations/tables. The article explores the correspondence between graph structures and join algorithms, focusing on how this perspective helps understand and optimize worst-case performance in database query processing.
Key quotes
· 4 pulledConsider the TPC-H query 5 (Local Supplier Volume) and just focus on the join part of the query.
If we create a graph for this query where nodes represent join variables (in SQL these are just join conditions as the notion of a join variable does not really exist in SQL) and where edges represent relations (tables), we get the following diagram.
Notice that this is a hypergraph as relations might participate in more than 2 join
TPC-H is standardised benchmark with very common business queries on a synthetic dataset.
You might also wanna read
A Formal Proof That Jira Is Turing-Complete via Minsky Machine Implementation
This article provides a formal proof that Jira (Atlassian's project-tracking tool) is Turing-complete by demonstrating how to build a Minsky
A Formal Proof That Jira Is Turing-Complete via Minsky Machine Implementation
This article provides a formal proof that Jira (Atlassian's project-tracking tool) is Turing-complete by demonstrating how to build a Minsky
How Shamir's Secret Sharing Algorithm Enables Threshold Cryptography
This article explains Adi Shamir's Secret Sharing algorithm, a cryptographic method published in 1979 that splits a secret into multiple pie
ente.com·6d agoThe History of Pipes, Forks, and Zombies in Unix Systems
This article discusses the history and concept of pipes in Unix systems, focusing on Doug McIlroy's original vision of coupling programs lik
Demystifying Floating Point Numbers: An Interactive Guide
An in-depth technical blog post that demystifies floating point numbers, explaining their internal representation and behavior. The author i
ciechanow.ski·1mo ago
Survey of Fast Hyperbolic Tangent Approximation Techniques for Neural Networks and Audio Processing
This article surveys various mathematical approximation techniques for the hyperbolic tangent (tanh) function, focusing on computational eff