From Pairwise Join to Global Perspective

Motivating Example: Different Orders of Pairwise JOINs

Table 1: Student_Teacher

Table 2: Teacher_Lab

Table 3: Lab_Device

Assume we have the 3 tables above in a database. We allow the same student to have multiple teachers, and the same teacher to guide multiple students, etc. Now, we want to see which devices each student can access via the laboratories their teachers belong to.

Any reader who has used SQL should know how to query this (the SQL below is simplified for demonstration and is not standard syntax):

SELECT * FROM Student_Teacher
    INNER JOIN Teacher_Lab ON Teacher
    INNER JOIN Lab_Device ON Lab

So, how do we obtain the execution results of this SQL statement in the database?

Since this involves three data tables, it is easy to see that we can perform Pairwise Joins. There are several options for the order:

Order 1 (Join Table 1 and Table 2 first)

Intermediate_Result = SELECT * FROM Student_Teacher INNER JOIN Teacher_Lab ON Teacher
Final_Result = SELECT * FROM Intermediate_Result INNER JOIN Lab_Device ON Lab

Order 2 (Join Table 2 and Table 3 first)

Intermediate_Result = SELECT * FROM Teacher_Lab INNER JOIN Lab_Device ON Lab
Final_Result = SELECT * FROM Student_Teacher INNER JOIN Intermediate_Result ON Teacher

Order 3 (Join Table 1 and Table 3 first)

Intermediate_Result = SELECT * FROM Student_Teacher CROSS JOIN Lab_Device
Final_Result = SELECT * FROM Intermediate_Result INNER JOIN Teacher_Lab ON Teacher, Lab

graph BT
    subgraph "Order 3"
        direction BT
        T3_A[("Student_Teacher")]:::table
        T3_C[("Lab_Device")]:::table
        T3_B[("Teacher_Lab")]:::table

        J3_1{{"CROSS JOIN (Cartesian)"}}:::op
        Res3["_Final Result_<br>JOIN ON Teacher & Lab"]:::result

        %% Cross join first
        T3_A --> J3_1
        T3_C --> J3_1
        
        %% Then join with the middle table
        J3_1 --> Res3
        T3_B --> Res3
    end

    subgraph "Order 2"
        direction BT
        T2_A[("Student_Teacher")]:::table
        T2_B[("Teacher_Lab")]:::table
        T2_C[("Lab_Device")]:::table

        J2_1{{"JOIN ON Lab"}}:::op
        Res2["_Final Result_<br>JOIN ON Teacher"]:::result

        T2_B --> J2_1
        T2_C --> J2_1
        
        T2_A --> Res2
        J2_1 --> Res2
    end
    
    subgraph "Order 1"
        direction BT
        T1_A[("Student_Teacher")]:::table
        T1_B[("Teacher_Lab")]:::table
        T1_C[("Lab_Device")]:::table
        
        J1_1{{"JOIN ON Teacher"}}:::op
        Res1["_Final Result_<br>JOIN ON Lab"]:::result

        T1_A --> J1_1
        T1_B --> J1_1
        
        J1_1 --> Res1
        T1_C --> Res1
        
        %% Labeling the final join edge for clarity
        linkStyle 2 stroke-width:2px,fill:none,stroke:green;
        linkStyle 3 stroke-width:2px,fill:none,stroke:green;
    end

Which one is better? Order 3 involves a CROSS JOIN (Cartesian product), so it can basically be ruled out immediately.

For any execution order, the input data (database/tables) is the same, and the output final result must also be the same. The only place where differences can occur is in the intermediate results. Let’s simulate the execution process.

The intermediate result for Order 1 is as follows, with a total of 6 rows:

The intermediate result for Order 2 is as follows, with a total of 3 rows:

Regardless of the order, the final result is as follows, with a total of 2 rows:

It is evident that Order 2 is superior because it outputs fewer intermediate results. These intermediate results not only take up memory but also participate in subsequent JOIN calculations, so obviously, the fewer the better.

This is exactly what modern Database Management Systems (DBMS) usually do: use Pairwise JOINs while selecting a potentially optimal JOIN order based on statistics and rules.

A More Intuitive View

We can represent this database as the path graph below, where each edge represents a row of data in a table:

graph LR
    %% Define styling to match the handwritten dot style
    classDef dot stroke-width:2px;

    %% Layer definitions for alignment
    subgraph Students
        S0(( S0 ))
        S1(( S1 ))
        S2(( S2 ))
    end

    subgraph Teachers
        T0(( T0 ))
        T1(( T1 ))
        T2(( T2 ))
        T3(( T3 ))
    end

    subgraph Labs
        L0(( L0 ))
        L1(( L1 ))
        L2(( L2 ))
        L3(( L3 ))
    end

    subgraph Devices
        GPU0(( GPU0 ))
        GPU1(( GPU1 ))
    end

    S0 --- T0
    S0 --- T1
    S1 --- T2
    S2 --- T2
    
    T0 --- L0
    T0 --- L1
    T1 --- L0
    T1 --- L1
    T2 --- L2
    T3 --- L3
    
    L2 --- GPU0
    L3 --- GPU0
    L3 --- GPU1

    %% Apply styling
    class S0,S1,S2,T0,T1,T2,T3,L0,L1,L2,L3,GPU0,GPU1 dot;

Consider Order 1, which looks for paths that can traverse all fields completely from Left to Right:

graph LR
    %% Define styling to match the handwritten dot style
    classDef dot stroke-width:2px;
    classDef thick-line stroke-width:10px;

    %% Layer definitions for alignment
    subgraph Students
        S0(( S0 ))
        S1(( S1 ))
        S2(( S2 ))
    end

    subgraph Teachers
        T0(( T0 ))
        T1(( T1 ))
        T2(( T2 ))
        T3(( T3 ))
    end

    subgraph Labs
        L0(( L0 ))
        L1(( L1 ))
        L2(( L2 ))
        L3(( L3 ))
    end

    subgraph Devices
        GPU0(( GPU0 ))
        GPU1(( GPU1 ))
    end

    S0 === T0
    S0 === T1
    S1 === T2
    S2 === T2
    
    T0 === L0
    T0 === L1
    T1 === L0
    T1 === L1
    T2 === L2
    T3 --- L3
    
    L2 === GPU0
    L3 --- GPU0
    L3 --- GPU1

    %% Apply styling
    class S0,S1,S2,T0,T1,T2,T3,L0,L1,L2,L3,GPU0,GPU1 dot;

The intermediate result of Order 1 contains three fields: “Student”, “Teacher”, and “Lab”. There are a total of 6 paths that can go from “Student” to “Lab” (Left to Right), which is exactly the number of rows in the intermediate result.

Similarly, consider Order 2, looking for paths from Right to Left:

graph RL
    %% Define styling to match the handwritten dot style
    classDef dot stroke-width:2px;
    classDef thick-line stroke-width:10px;

    %% Layer definitions for alignment
    subgraph Students
        S0(( S0 ))
        S1(( S1 ))
        S2(( S2 ))
    end

    subgraph Teachers
        T0(( T0 ))
        T1(( T1 ))
        T2(( T2 ))
        T3(( T3 ))
    end

    subgraph Labs
        L0(( L0 ))
        L1(( L1 ))
        L2(( L2 ))
        L3(( L3 ))
    end

    subgraph Devices
        GPU0(( GPU0 ))
        GPU1(( GPU1 ))
    end
    
    T0 --- S0
    T1 --- S0
    T2 === S1
    T2 === S2

    L0 --- T0
    L1 --- T0
    L0 --- T1
    L1 --- T1
    L2 === T2
    L3 === T3
    
    GPU0 === L2
    GPU0 === L3
    GPU1 === L3

    %% Apply styling
    class S0,S1,S2,T0,T1,T2,T3,L0,L1,L2,L3,GPU0,GPU1 dot;

The number of rows in the intermediate result for Order 2 is also equal to the number of paths from the “Device” field to the “Teacher” field.

In fact, whether choosing Left-to-Right or Right-to-Left, both orders produce some waste in the intermediate results:

• When going Left-to-Right, reaching L0 and L1 is a dead end (cannot reach a Device).
• When going Right-to-Left, reaching T3 is a dead end (cannot reach a Student).

Taking it to the Extreme

graph LR
    %% Define styling to match the handwritten dot style
    classDef dot stroke-width:2px;
    classDef thick-line stroke-width:4px;

    %% Layer definitions for alignment
    subgraph Students
        S0(( S0 ))
        S1(( S1 ))
        S2(( S2 ))
        S3(( S3 ))
        S4(( S4 ))
    end

    subgraph Teachers
        T0(( T0 ))
        T1(( T1 ))
        T2(( T2 ))
        T3(( T3 ))
    end

    subgraph Labs
        L0(( L0 ))
        L1(( L1 ))
        L2(( L2 ))
        L3(( L3 ))
    end

    subgraph Devices
        GPU0(( GPU0 ))
        GPU1(( GPU1 ))
        GPU2(( GPU2 ))
        GPU3(( GPU3 ))
        GPU4(( GPU4 ))
    end

    S0 --- T0
    S1 --- T0
    S2 --- T0
    S3 --- T0

    T0 --- L0
    T0 --- L1
    
    T1 --- L2
    T2 --- L2
    
    L2 --- GPU0
    L2 --- GPU1
    L2 --- GPU2
    L2 --- GPU3
    
    S4 --- T3 --- L3 --- GPU4

    %% Apply styling
    class S0,S1,S2,S3,S4,T0,T1,T2,T3,L0,L1,L2,L3,GPU0,GPU1,GPU2,GPU3,GPU4 dot;

The example shown above is very extreme: almost all students (S0-S3) chose the same teacher (T0), and almost all devices (GPU0-GPU3) are concentrated in the same lab (L2). However, the most popular teacher (T0) belongs to labs (L0/L1) that don’t have a single machine…

Assuming this is reality, it is easy to see that after performing the same JOIN query on this database instance, the result should contain only one row:

However, if we adopt the “Pairwise JOIN” scheme, regardless of which JOIN order is chosen, the intermediate results will have 9 rows (interactions between T0’s students and L2’s devices or similar paths). When the data volume is larger and similar Data Skew exists, the waste of computing resources can be immense.

What should we do?

Global Perspective

Let’s continue to observe this extreme example. What causes the waste in intermediate results are those dead-end paths. So, is it possible to filter out these dead ends before generating intermediate results?

Yes, but the Pairwise JOIN method obviously won’t work; we need a Global Perspective.

The cause of data expansion is that data rows joining on the same field value in two tables create a Cartesian product. Therefore, we need to avoid performing a JOIN (or strictly speaking, avoid performing an INNER JOIN) before completing the filtering.

Why speak strictly? Because we actually still have to JOIN, but it is a special kind of JOIN: SEMI JOIN. It is perfectly suited for this filtering task.

First Pass: Left to Right

To filter out rows in the right table that cannot JOIN.

Teacher_Lab_1 = SELECT * FROM Teacher_Lab WHERE EXISTS(
    SELECT * FROM Student_Teacher WHERE (Student_Teacher.Teacher = Teacher_Lab.Teacher)
)

Lab_Device_1 = SELECT * FROM Lab_Device WHERE EXISTS(
    SELECT * FROM Teacher_Lab_1 WHERE (Teacher_Lab_1.Lab = Lab_Device.Lab)
)

graph LR
    %% Define styling to match the handwritten dot style
    classDef dot stroke-width:2px;
    classDef dotrm fill:#aaa,stroke:#666,stroke-width:2px;

    %% Layer definitions for alignment
    subgraph Students
        S0(( S0 ))
        S1(( S1 ))
        S2(( S2 ))
        S3(( S3 ))
        S4(( S4 ))
    end

    subgraph Teachers
        T0(( T0 ))
        T1(( T1 ))
        T2(( T2 ))
        T3(( T3 ))
    end

    subgraph Labs
        L0(( L0 ))
        L1(( L1 ))
        L2(( L2 ))
        L3(( L3 ))
    end

    subgraph Devices
        GPU0(( GPU0 ))
        GPU1(( GPU1 ))
        GPU2(( GPU2 ))
        GPU3(( GPU3 ))
        GPU4(( GPU4 ))
    end

    S0 --- T0
    S1 --- T0
    S2 --- T0
    S3 --- T0

    T0 --- L0
    T0 --- L1
    
    T1 ~~~ L2
    T2 ~~~ L2
    
    L2 ~~~ GPU0
    L2 ~~~ GPU1
    L2 ~~~ GPU2
    L2 ~~~ GPU3
    
    S4 --- T3 --- L3 --- GPU4

    %% Apply styling
    class S0,S1,S2,S3,S4,T0,T3,L0,L1,L3,GPU4 dot;
    class T1,T2,L2,GPU0,GPU1,GPU2,GPU3 dotrm;

We guarantee that the filtered data in the right-side table can definitely JOIN with all data tables to its left (including non-adjacent ones). Therefore, after completing the first pass of filtering, the data remaining in the right-most table is guaranteed to participate in the final result.

Second Pass: Right to Left

To filter out rows in the left table that cannot JOIN.

Teacher_Lab_2 = SELECT * FROM Teacher_Lab_1 WHERE EXISTS(
    SELECT * FROM Lab_Device_1 WHERE (Teacher_Lab_1.Lab = Lab_Device_1.Lab)
)

Student_Teacher_1 = SELECT * FROM Student_Teacher WHERE EXISTS(
    SELECT * FROM Teacher_Lab_2 WHERE (Student_Teacher.Teacher = Teacher_Lab_2.Teacher)
)

graph LR
    %% Define styling to match the handwritten dot style
    classDef dot stroke-width:2px;
    classDef dotrm fill:#aaa,stroke:#666,stroke-width:2px;

    %% Layer definitions for alignment
    subgraph Students
        S0(( S0 ))
        S1(( S1 ))
        S2(( S2 ))
        S3(( S3 ))
        S4(( S4 ))
    end

    subgraph Teachers
        T0(( T0 ))
        T1(( T1 ))
        T2(( T2 ))
        T3(( T3 ))
    end

    subgraph Labs
        L0(( L0 ))
        L1(( L1 ))
        L2(( L2 ))
        L3(( L3 ))
    end

    subgraph Devices
        GPU0(( GPU0 ))
        GPU1(( GPU1 ))
        GPU2(( GPU2 ))
        GPU3(( GPU3 ))
        GPU4(( GPU4 ))
    end

    S0 ~~~ T0
    S1 ~~~ T0
    S2 ~~~ T0
    S3 ~~~ T0

    T0 ~~~ L0
    T0 ~~~ L1
    
    T1 ~~~ L2
    T2 ~~~ L2
    
    L2 ~~~ GPU0
    L2 ~~~ GPU1
    L2 ~~~ GPU2
    L2 ~~~ GPU3
    
    S4 --- T3 --- L3 --- GPU4

    %% Apply styling
    class S4,T3,L3,GPU4 dot;
    class S0,S1,S2,S3,T0,L0,L1 dotrm;
    class T1,T2,L2,GPU0,GPU1,GPU2,GPU3 dotrm;

We guarantee that the filtered data in the left-side table can definitely JOIN with all data tables to its right (including non-adjacent ones). Since the first pass guaranteed the right-most data participates in the final result, the second pass ensures that the remaining data in ALL tables will participate in the final result.

Third Pass: Left to Right

To complete the JOIN.

At this point, all paths that do not participate in the final JOIN result have been cleared away. We can now safely perform Pairwise JOINs.

Summary: Yannakakis Algorithm (Simplified)

What is introduced here is the Yannakakis Algorithm specialized for linear JOIN queries. Compared to Pairwise JOIN, its advantage lies in being sensitive to the result size.

The complexity of Pairwise JOIN is independent of the JOIN result size. Therefore, even if the final result is actually very small, it may produce a massive amount of intermediate results. For the database instance mentioned above, the time complexity of Pairwise JOIN is $O(N^2)$, whereas the time complexity of the Yannakakis algorithm shown here is $O(N+OUT)$, where $N$ is the data size and $OUT$ is the size of the JOIN result.

The worst-case time complexity for both is consistent. Assuming there are $K$ data tables with no common attributes, equivalent to doing a full Cartesian product: Pairwise JOIN time complexity is $O(N^K)$, and Yannakakis time complexity is $O(N+OUT)$, where $OUT=N^K$.

JOIN algorithms with $O(N+OUT)$ complexity are also known as Output-Optimal algorithms. Regardless of the JOIN algorithm, one must read all the data ($O(N)$) and output all the results ($O(OUT)$), so $O(N+OUT)$ is already optimal for a specific output size.