DPhyp Join Order Algorithm

[mkleen]

State-of-the-Art for Join Ordering is the DPhyp algorithm:

• Generated order guaranteed to be optimal.
• Enumerates all possibly optimal join orders without cross products.
• Optimization for linear queries is which scales up to 100 relations.
• Optimization for clique queries is
• which scales up to 14 relations.
• Widely used in many database systems.

Roadmap:

• Improve cardinality estimation for joins
• Find test data and setup the tests first
• Implement simplified DPhyp version which only supports inner-joins
• Extend to other join types

References:
https://15721.courses.cs.cmu.edu/spring2020/papers/20-optimizer2/p539-moerkotte.pdf

[seut]

It's currently not completely clear what is missing in our planner to support any join order algorithm, like do our existing join operators (join pairs) have enough information declared, etc. Please add more information.

[mkleen]

From my perspective, the following parts are missing:

• Make Logical Plans identifiable, add ids to logical plans. The algorithm uses binary set operations to find the solution, each operator is represented by a number. See Add ids to logical plans #13525
• Add a mechanism to convert a Logical Operator Tree to a Join Graph and back to Logical Operator Tree.

[mkleen]

This is a general workflow how I would structure it:

flowchart TD
    A[Sql] -->B(Analyzed Statement)
    B -->C(Planner)
    C -->D(Logical Plan Tree)
    D -->E(Enter Optimizer)
    E -->F(Push down Filters/Projections for Cardinality Estimates)
    F -->G(Match Join Operators)
    G -->H(Build Join Graph)
    H -->I(Run Join Order Algorithm)
    I -->J(Rebuild Logical Plan Tree with new Join Order)
    J -->K( Optimize Logical Plan Tree further)
    K -->L(Build Execution Plan)

[mkleen]

It's currently not completely clear what is missing in our planner to support any join order algorithm, like do our existing join operators (join pairs) have enough information declared, etc. Please add more information.

The Join Reordering will be integrated into an optimizer rule and operate on Logical Plans such as Collect/JoinPlan etc. The Logical Plans consist of all information to build a Graph.