# Presto 两种 JOIN 算法实现

## JOIN 的实现

### Probe Table

Presto 使用优化后的逻辑计划中的右表作为构建表，将逻辑计划中的左表作为探测表。请注意，逻辑计划中的表不必与它们在 SQL 查询中的顺序相同。Presto 有一些基于成本的优化器，它们可以重新排序连接以将最小的表（即构建表）保留在右侧，以便它可以放入内存中。如果连接重新排序优化器被禁用或连接器特定的统计信息（例如 Hive 统计信息）被禁用，则 Presto 将不会对连接查询重新排序。在这种情况下，建议将最小的表保留在连接的右侧，以便 Presto 可以将其用作构建表。

## JOIN 算法

### Nested Loop Algorithm

```public class IteblogNestedLoop {
public static void main(String[] args) {
// Construct two arrays
int[] tableA = {1, 2, 3, 4, 5, 6};
int[] tableB = {10, 20, 30, 40};

// Nested loop to print the Cartesian product of two arrays
for (int x : tableA) {
for (int y : tableB) {
System.out.println(x + ", " + y);
}
}
}
}
```

### Hash Join Algorithm

```class Order {
String orderKey;
String custKey;
double totalPrice;

public Order(String orderKey, String custKey, double totalPrice) {
this.orderKey = orderKey;
this.custKey = custKey;
this.totalPrice = totalPrice;
}

@Override
public String toString() {
return "Order: " + orderKey + ", " + custKey + ", " + totalPrice;
}
}

class Customer {
String custKey;
String name;

public Customer(String custKey, String name) {
this.custKey = custKey;
this.name = name;
}

@Override
public String toString() {
return "Customer: " + name + ", " + custKey;
}
}
```

```import java.util.*;

public class IteblogHashJoin {
public static void main(String[] args) {
List<Customer> probe = List.of(new Customer("c_001", "Alice"),
new Customer("c_002", "Bob"),
new Customer("c_003", "David"));

List<Order> build = List.of(new Order("o_01", "c_001", 100.0),
new Order("o_01", "c_001", 100.0),
new Order("o_02", "c_001", 150.0),
new Order("o_03", "c_002", 90.0),
new Order("o_04", "c_003", 120.0));

// Nested loop join
for (Customer customer : probe) {
for (Order order : build) {
if (Objects.equals(customer.custKey, order.custKey)) {
System.out.println(customer + " -> " + order);
}
}
}
}
}
```

```import java.util.*;

public class IteblogHashJoin {
public static void main(String[] args) {
List<Customer> probe = List.of(new Customer("c_001", "Alice"),
new Customer("c_002", "Bob"),
new Customer("c_003", "David"));

List<Order> build = List.of(new Order("o_01", "c_001", 100.0),
new Order("o_01", "c_001", 100.0),
new Order("o_02", "c_001", 150.0),
new Order("o_03", "c_002", 90.0),
new Order("o_04", "c_003", 120.0));

// Build the hash map index
Map<Integer, List<Order>> index = new Hashtable<>();
for (Order order : build) {
int hash = Objects.hash(order.custKey);
index.putIfAbsent(hash, new LinkedList<>());
index.get(hash).add(order);
}

// Hash Join algorithm
for (Customer customer : probe) {
int hash = Objects.hash(customer.custKey);
List<Order> orders = index.get(hash);
if (orders != null) {
for (Order order : orders) {
if (Objects.equals(customer.custKey, order.custKey)) {
System.out.println(customer + " -> " + order);
}
}
}
}
}
}
```

```SELECT *
FROM iteblog.customer c
LEFT JOIN iteblog.orders o
ON c.custkey=o.orderkey;
```

```SELECT o.orderkey, l.linenumber
FROM iteblog.orderkey o
LEFT JOIN iteblog.lineitem l
ON o.orderdate < l.shipdate;
```

Hash Join 算法不适用于具有不等式约束的 join 条件。 首先，很难提出一个完美的散列算法来保持输入的不等式属性（即给定 x > b 并不能保证 hash(a) > hash(b)）。 其次，即使我们提出了一个满足不等式要求的散列函数，我们也不能简单地连接一个桶中的所有值。要加入不相等的行，应该匹配大于/小于给定列的每一行。 因此，Presto 使用带 filter 的嵌套循环算法而不是散列连接算法来执行具有非等连接条件的连接。

### Merge Join

Merge Join 算法来自著名的 Merge-Sort 算法。归并排序算法有两个阶段：排序和合并。 假设两个数组已经排序，它们可以以 O(n) 的时间复杂度合并。Presto 可以通过使用 equijoin criteria 中使用的列对构建表和探测表进行排序，然后通过执行合并操作来实现该算法。 忽略排序部分，merge join 算法的性能有望优于上述算法，但 Presto 社区发现它需要在内存中对两个表进行排序，这在大数据世界中很耗时，考虑到有限的内存，甚至可能是不可行的。但是，如果有机会在底层数据源中对数据进行排序，则合并连接算法可能是一个更好的候选算法。