# Merge Join
#### 算子说明
合并连接（Merge Join）是一种高效的连接方法，它依赖于排序操作。在进行合并连接时，GaussDB会对两个表的连接字段进行排序，然后同步扫描两个表，寻找匹配的行。 Merge Join的时间复杂度为O(n+m), 其中n和m分别代表两个表的行数。然而，如果需要排序操作，这个排序操作的时间复杂度可能会达到max(O(logn), O(logm)), 这通常会比直接的Merge Join操作更加耗时。 在GaussDB中，优化器更倾向于选择Hash Join，即使需要连接的两张表已经经过排序。
#### 典型场景
- 当两个表的大小接近时。
- 当两个表的连接字段已经被排序或者已经有序时，比如通过索引保持排序。
 
#### 示例
示例：两表做连接操作，且两表大小接近。
```
--数据准备。 
gaussdb=# DROP TABLE IF EXISTS t1;
gaussdb=# DROP TABLE IF EXISTS t2;
gaussdb=# CREATE TABLE t1(id int,info text); 
CREATE TABLE 
gaussdb=# CREATE TABLE t2(id int,info text); 
CREATE TABLE 
gaussdb=# INSERT INTO t2 SELECT generate_series(1,100000),'bill'||generate_series(1,100000); 
INSERT 0 100000 
gaussdb=# INSERT INTO t1 SELECT generate_series(1,100000),'bill'||generate_series(1,100000); 
INSERT 0 100000
--收集统计信息。
gaussdb=# ANALYZE t1;
gaussdb=# ANALYZE t2;
--执行结果。 
gaussdb=# EXPLAIN SELECT /*+ MERGEJOIN(t2 t1) */ * FROM t2 JOIN t1 ON (t1.id=t2.id); 
                                 QUERY PLAN
----------------------------------------------------------------------------
 Streaming (type: GATHER)  (cost=9352.82..15036.32 rows=100000 width=26)
   Node/s: All datanodes
   ->  Merge Join  (cost=9348.82..10348.82 rows=100000 width=26)
         Merge Cond: (t2.id = t1.id)
         ->  Sort  (cost=4674.41..4799.41 rows=100000 width=13)
               Sort Key: t2.id
               ->  Seq Scan on t2  (cost=0.00..772.00 rows=100000 width=13)
         ->  Sort  (cost=4674.41..4799.41 rows=100000 width=13)
               Sort Key: t1.id
               ->  Seq Scan on t1  (cost=0.00..772.00 rows=100000 width=13)
(10 rows)
--删除表。
gaussdb=# DROP TABLE IF EXISTS t1;
gaussdb=# DROP TABLE IF EXISTS t2;
```
上述示例中，Merge Join算子输出信息如下所示。
| 信息名称       | 含义                                                                |
|:---|:---|
| Merge Join | 算子的名称。                                                            |
| Merge Cond | 算子Merge join的连接谓词，示例中条件为t2.id等于t1.id，在查询执行时，满足这些条件的行会被包含在最终的结果集中。 |
   
**示例：**当两个表的连接字段已经被排序或者已经有序时，比如通过索引保持排序。
```
--数据准备。 
gaussdb=# DROP TABLE IF EXISTS t1;
gaussdb=# DROP TABLE IF EXISTS t2;
gaussdb=# CREATE TABLE t1(id int,info text); 
CREATE TABLE 
gaussdb=# CREATE TABLE t2(id int,info text); 
CREATE TABLE 
gaussdb=# CREATE INDEX t1_k on t1(id);
CREATE INDEX
gaussdb=# INSERT INTO t2 SELECT generate_series(1,100000),'bill'||generate_series(1,100000); 
INSERT 0 100000 
gaussdb=# INSERT INTO t1 SELECT generate_series(1,100000),'bill'||generate_series(1,100000); 
INSERT 0 100000
gaussdb=# SET enable_fast_query_shipping = off;
SET
--收集统计信息。
gaussdb=# ANALYZE t1;
gaussdb=# ANALYZE t2;
--执行结果。 
gaussdb=# 
EXPLAIN SELECT /*+ MERGEJOIN(t2 t1) */ * FROM t2 JOIN t1 ON (t1.id=t2.id);
                              QUERY PLAN
-----------------------------------------------------------------------
 Streaming (type: GATHER)  (cost=27.37..27.91 rows=20 width=72)
   Node/s: All datanodes
   ->  Merge Join  (cost=26.74..26.97 rows=20 width=72)
         Merge Cond: (t2.id = t1.id)
         ->  Sort  (cost=13.37..13.40 rows=21 width=36)
               Sort Key: t2.id
               ->  Seq Scan on t2  (cost=0.00..13.13 rows=20 width=36)
         ->  Sort  (cost=13.37..13.40 rows=21 width=36)
               Sort Key: t1.id
               ->  Seq Scan on t1  (cost=0.00..13.13 rows=20 width=36)
(10 rows)
--删除。
gaussdb=# DROP TABLE t1,t2;
```