PostgreSQL JOIN实践及原理

最近项目使用了PostgreSQL 简单学习join语法以及原理，以后有时间搞一下SQLite源码。

PostgreSQL  JOIN 子句用于把来自两个或多个表的行结合起来，基于这些表之间的共同字段。

在 PostgreSQL 中，JOIN 有五种连接类型：

CROSS JOIN ：交叉连接

INNER JOIN：内连接

LEFT OUTER JOIN：左外连接

RIGHT OUTER JOIN：右外连接

FULL OUTER JOIN：全外连接

1.数据准备

创建company表和department表 其中company表存储员工基本信息 department表存储部门信息。

company表定义以及初始化数据如下：

DROP TABLE COMPANY;

CREATE TABLE COMPANY(

   ID INT PRIMARY KEY     NOT NULL,

   NAME           TEXT    NOT NULL,

   AGE            INT     NOT NULL,

   ADDRESS        CHAR(50),

   SALARY         REAL

);

INSERT INTO COMPANY (ID,NAME,AGE,ADDRESS,SALARY) VALUES (1, 'Paul', 32, 'California', 20000.00 );

INSERT INTO COMPANY (ID,NAME,AGE,ADDRESS,SALARY) VALUES (2, 'Allen', 25, 'Texas', 15000.00 );

INSERT INTO COMPANY (ID,NAME,AGE,ADDRESS,SALARY) VALUES (3, 'Teddy', 23, 'Norway', 20000.00 );

INSERT INTO COMPANY (ID,NAME,AGE,ADDRESS,SALARY) VALUES (4, 'Mark', 25, 'Rich-Mond ', 65000.00 );

INSERT INTO COMPANY (ID,NAME,AGE,ADDRESS,SALARY) VALUES (5, 'David', 27, 'Texas', 85000.00 );

INSERT INTO COMPANY (ID,NAME,AGE,ADDRESS,SALARY) VALUES (6, 'Kim', 22, 'South-Hall', 45000.00 );

INSERT INTO COMPANY VALUES (7, 'James', 24, 'Houston', 10000.00 );

INSERT INTO COMPANY VALUES (8, 'Paul', 24, 'Houston', 20000.00);

INSERT INTO COMPANY VALUES (9, 'James', 44, 'Norway', 5000.00);

INSERT INTO COMPANY VALUES (10, 'James', 45, 'Texas', 5000.00);

department表定义以及初始化如下：

CREATE TABLE DEPARTMENT(

   ID INT PRIMARY KEY      NOT NULL,

   DEPT           CHAR(50) NOT NULL,

   EMP_ID         INT      NOT NULL

);

INSERT INTO DEPARTMENT (ID, DEPT, EMP_ID) VALUES (1, 'IT Billing', 1 );

INSERT INTO DEPARTMENT (ID, DEPT, EMP_ID) VALUES (2, 'Engineering', 2 );

INSERT INTO DEPARTMENT (ID, DEPT, EMP_ID) VALUES (3, 'Finance', 7 );

2.连接操作

2.1 交叉连接

交叉连接（CROSS JOIN）把第一个表的每一行与第二个表的每一行进行匹配。如果两个输入表分别有 x 和 y 行，则结果表有 x*y 行。

SELECT EMP_ID, NAME, DEPT FROM COMPANY CROSS JOIN DEPARTMENT;

其相应查询计划如下所示：

2.2 内连接

内连接（INNER JOIN）根据连接谓词结合两个表（table1 和 table2）的列值来创建一个新的结果表。查询会把 table1 中的每一行与 table2 中的每一行进行比较，找到所有满足连接谓词的行的匹配对。当满足连接谓词时，A 和 B 行的每个匹配对的列值会合并成一个结果行。内连接（INNER JOIN）是最常见的连接类型，是默认的连接类型。INNER 关键字是可选的。

SELECT EMP_ID, NAME, DEPT FROM COMPANY INNER JOIN DEPARTMENT ON COMPANY.ID = DEPARTMENT.EMP_ID;

2.3 左外连接

对于左外连接，首先执行一个内连接。然后，对于表 T1 中不满足表 T2 中连接条件的每一行，其中 T2 的列中有 null 值也会添加一个连接行。因此，连接的表在 T1 中每一行至少有一行。

2.4 右外连接

首先，执行内部连接。然后，对于表T2中不满足表T1中连接条件的每一行，其中T1列中的值为空也会添加一个连接行。这与左联接相反;对于T2中的每一行，结果表总是有一行。

2.5 外连接

首先，执行内部连接。然后，对于表 T1 中不满足表 T2 中任何行连接条件的每一行，如果 T2 的列中有 null 值也会添加一个到结果中。此外，对于 T2 中不满足与 T1 中的任何行连接条件的每一行，将会添加 T1 列中包含 null 值的到结果中。

由以上操作可知  大多数连接会使用Hash Join算法来实现。postgreSQL中join算法有三种nested loop join merge join 以及hash join

3.连接原理

3.1 nested loop join

nested loop join: The right relation is scanned once for every row found in the left relation. This strategy is easy to implement but can be very time consuming. (However, if the right relation can be scanned with an index scan, this can be a good strategy. It is possible to use values from the current row of the left relation as keys for the index scan of the right.)

EXPLAIN SELECT * FROM COMPANY JOIN DEPARTMENT ON DEPARTMENT.EMP_ID = COMPANY.ID WHERE company."id" = 1;

1.     表company按照id来过滤得到结果

2.     对于过滤后结果每一行，利用id从department表中进行匹配

3.2 merge join

merge join: Each relation is sorted on the join attributes before the join starts. Then the two relations are scanned in parallel, and matching rows are combined to form join rows. This kind of join is more attractive because each relation has to be scanned only once. The required sorting might be achieved either by an explicit sort step, or by scanning the relation in the proper order using an index on the join key.

set enable_hashjoin=off; 

EXPLAIN SELECT * FROM COMPANY JOIN DEPARTMENT ON DEPARTMENT.emp_id = COMPANY.ID;

1. 首先company表关联字段id是有序的 直接索引扫描
2. Deparpment 首先按照emp_id排序  然后执行merge join

3.3 hash join

hash join: the right relation is first scanned and loaded into a hash table, using its join attributes as hash keys. Next the left relation is scanned and the appropriate values of every row found are used as hash keys to locate the matching rows in the table.

set enable_hashjoin=on; 

EXPLAIN SELECT * FROM COMPANY JOIN DEPARTMENT ON DEPARTMENT.emp_id = COMPANY.ID WHERE company."id" = 1;

EXPLAIN SELECT * FROM COMPANY JOIN DEPARTMENT ON DEPARTMENT.emp_id = COMPANY.ID WHERE company.age = 32;

首先顺序扫描department表 构建hash表 key=department.emp_id 即关联字段，

然后顺序扫描company表  用company表Id来匹配hash表key 如果匹配成功 则输出。

hash join和merge join被关联的两个表都只扫描一次, nested loop join则被关联的表其中一个扫描一次, (如果前一个表的扫描结果有多行输出)另一个扫描多次.

HASH JOIN原理

参考一下hash join实现源码：

将主驱动表的关联字段作为key，主驱动表需要的字段作为value来构建hash表。

遍历被驱动表的每一行 计算该行是否与hash表中key相同 如果key相同则将被驱动表相应字段和命中hash表key对应的value一起输出，作为结果中的一行。由于hash表的使用，被驱动表的每一行查找时间复杂度为常数。

for (j = 0; j < length(inner); j++)

　　hash_key = hash(inner[j]);

　　append(hash_store[hash_key], inner[j]);

for (i = 0; i < length(outer); i++)

　　hash_key = hash(outer[i]);

　　for (j = 0; j < length(hash_store[hash_key]); j++)

　　　　if (outer[i] == hash_store[hash_key][j])

　　　　　　output(outer[i], inner[j]);

解释如下：

//利用 inner 表， 来构造 hash 表(放在内存里)           

for (j = 0; j < length(inner); j++)           

{           

    hash_key = hash(inner[j]);       

    append(hash_store[hash_key], inner[j]);       

}                      

//对 outer 表的每一个元素， 进行遍历           

for (i = 0; i < length(outer); i++)           

{           

    //拿到 outer 表中的  某个元素， 进行 hash运算， 得到其 hash_key 值       

    hash_key = hash(outer[i]);          

    //用上面刚得到的 hash_key值， 来 对 hash 表进行 探测（假定hash表中有此key 值）       

    //采用 length (hash_store[hash_Key])  是因为，hash算法构造完hash 表后，有可能出现一个key值处有多个元素的情况。           

    //对 拥有相同 的 （此处是上面刚运算的，特定的）hash_key 值的各个元素的遍历       

    for (j = 0; j < length(hash_store[hash_key]); j++)       

    {       

        //如果找到了匹配值，则输出一行结果   

        if (outer[i] == hash_store[hash_key][j])   

            output(outer[i], inner[j]);

    }       

}