Join $T_1 \bowtie T_2$

Single-column equi-join#

Given

• tables $T1 = (D_1, C_1,R_1), T_2 = (D_2, C_2, R_2))$
• column indexes: $j_1 \in \{1, ..., |C_1|\}, j2 \in \{1,...,|C_2|\}$

Join computes a table $T$ with:

• C = (C_1,C_2) D = (D_1,D_2)
• $R = \{(r_1,r_2) \in R_1 \times R_2\ |\ r_1[j_1] = r_2[j_2]\}$

Inner join#

Left Outer Join#

Right Outer Join#

Natural Join#

A natural join between two tables is an equi-join between two tables that considers all columns as join columns that have the same name in both tables

Spatial Join#

This is a non-equi join that joins two tables based on a spacial property.

Computing#

Hash Join#

Compute a hash map that maps each value to the set of row indices containing this value in the join col. Then iter over the rows of the second table adding each row from the row_set.

1. let $x_1, ..., x_n$ be the rows of the first Table X
2. let K = {x_1[j_1], …, x_n[j_1]} be the set of distinct values of col $j_1$
3. Compute hash map $H$, wich maps each $k \in K$ to the set of indeces of rows of X containing k in column $j_1$.
4. Let $y_1,...,y_n$ be the rows of the second table $Y$
5. For each row $y_j$, if $y_j[j_2] \in K$, then for each $i \in H[y]$ add row $(x_i, y_j)$ to the result

Runtime $C_I \cdot n_1 + C_L \cdot n_2 + C_C \cdot n \cdot k$ where:

• $C_I$: average cost to insert in hashmap H
• $C_L$: average cost to insert into hashmap H
• $C_C$ average cost for copying a value to the result

Merge Join#

If the values in the join columns are ordered then we can compute the join with the Zipper algorithm. This is the same algorithm as the intersection of sorted lists used for inverted index queries in Lecture 1 (Slides 05, p. 13). The one difference: whenever a value of $X$ matches a value of $Y$, output the pairs with all rows of $Y$ that have the same value, since join columns may contain duplicates.