DP-JOA
Join optimization is the process of optimizing the joining, or combining, of two or more tables in a database.
Here is a simple join optimization algorithm (JOA) being implemented to find the lowest estimated cost join plan
for a natural chain join query using dynamic programming (DP).
Join Constraint
Consider Relations: R0 ⋈ R1 ⋈ R2 whose cardinality is 5, 10, 15 respectively:
Fullness
Each relation should appear once.
Cartesian Product-free
No join of two relations that don’t share a common column. So the following graph is invalid:
Left Relation Join
In order for the join be evaluated using HashJoin algorithm later, the relation with smaller cardinality is on the left. So the following graph is invalid:
Usage
$ python main.py --query sample
For this sample example, there are three relationships, each one with cardinality of 5, 10, 15, and R1 has foreign key to R2, R2 has the foreign key to R3. It prints a the lowest cost join tree graph:
R0
JO(5)
R1
JO(5)
R2
Where it indicates a join of R0 and R1 first, with an estimated cardinality of 5, then join it with R2 with a total cardinality of 5.
