apache / apache/datafusion

Consider adding a JoinGraph structure for representing joins

Open
#17,719 18 comments 6 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

This is part of a larger discussion for improving the APIs for Join planning in DataFusion
- https://github.com/apache/datafusion/issues/17718

Specifically, many more sophisticated join ordering algorithms rely on a data structure called a "JoinGraph" (defined below)

In DataFusin terms, a JoinGraph could be formed from any tree of `LogicalPlan::Join` or corresponding PhysicalPlan

Some ideas:
```rust
/// represents a join graph
struct JoinGraph {
...
}

impl JoinGraph {
// make a new join graph from a plan
// NOTE this maybe should be in terms of physical plans / `Arc`
fn new_from_plan(logical_plan: LogicalPlan) -> Result {..}
...
// create a new plan from a join grap
fn into_plan(self) -> Result
}
```

### Join Graphs
Quoting a pretty good [Google AI summary](https://www.google.com/search?q=joingraph+data+structure+database+definition+%28not+graph+database):

A join graph in the context of relational databases is a data structure that represents the relationships and potential join operations between tables in a relational database schema.

Here's a breakdown of its definition:
* [Vertices (Nodes): ](https://www.google.com/search?sca_esv=3cba3ff7c6207a53&cs=1&q=Vertices+%28Nodes%29)Each vertex in a join graph corresponds to a table (or relation) in the relational database schema.
* [Edges: ](https://www.google.com/search?sca_esv=3cba3ff7c6207a53)An edge between two vertices (tables) signifies a join relationship between those tables (e.g an equality predicate).
* [Edge Labels (Join Conditions): ](https://www.google.com/search?sca_esv=3cba3ff7c6207a53&cs=1&q=Edge+Labels+%28Join+Conditions%29)Edges are labeled with the specific join conditions that define how the connected tables are to be joined. These conditions specify the attributes that must match for a successful join (e.g., TableA.ID = TableB.TableA_ID).

Join graphs are used to:
* [Plan Query Execution: ](https://www.google.com/search?sca_esv=3cba3ff7c6207a53&cs=1&q=Plan+Query+Execution)Database query optimizers can use join graphs to identify efficient ways to execute queries involving multiple joins.

For example, TPCH Q3 is expressed in SQL like this:
```sql
select
l_orderkey,
sum(l_extendedprice * (1 - l_discount)) as revenue,
o_orderdate,
o_shippriority
from
customer,
orders,
lineitem
where
c_mktsegment = 'BUILDING'
and c_custkey = o_custkey
and l_orderkey = o_orderkey
and o_orderdate < date '1995-03-15'
and l_shipdate > date '1995-03-15'
group by
l_orderkey,
o_orderdate,
o_shippriority
order by
revenue desc,
o_orderdate
limit 10;
```

It can be represented with the following JoinGraph (the edges of the arrows represent foreign key --> Primary Key constraints)

```mermaid
graph TD
customer["customer"]
orders["orders"]
lineitem["lineitem"]

customer -->|c_custkey = o_custkey| orders
orders -->|o_orderkey = l_orderkey| lineitem
```

Contributor guide

Open the contributing guide

Research direction

Start with issue #17718 and the existing LogicalPlan::Join and corresponding PhysicalPlan representations to resolve whether the structure belongs at the logical or physical level. Map the required JoinGraph semantics and conversion boundaries before proposing an API; done means the scope and representation are agreed and supported by the plan conversions.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust, sql
Domain
databases
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.