在线午夜精品自拍小视频_无码av无码专区线_亚洲无码精品人妻_人人澡欧美一区

圖解數(shù)據(jù)庫連接查詢（JOIN）的三種實(shí)現(xiàn)算法： MySQL、Oracle、SQL Server 等

作者: 不剪發(fā)的Tony老師
畢業(yè)于北京航空航天大學(xué)，十多年數(shù)據(jù)庫管理與開發(fā)經(jīng)驗(yàn)，目前在一家全球性的金融公司從事數(shù)據(jù)庫架構(gòu)設(shè)計(jì)。CSDN學(xué)院簽約講師以及GitChat專欄作者。csdn上的博客收藏于以下地址：https://tonydong.blog.csdn.net



 

文章目錄

        嵌套循環(huán)連接
        哈希連接
        排序合并連接
        總結(jié)

An SQL query walks into a bar and sees two tables. He walks up to them and asks ‘Can I join you?’
一個(gè) SQL 查詢走進(jìn)酒吧看到兩張桌子（table），走到它們面前問“我可以和你們坐在一起（join）嗎？”

SQL 連接查詢（JOIN）可以同時(shí)獲取多個(gè)表中的關(guān)聯(lián)數(shù)據(jù)。例如，查看某個(gè)完整的訂單數(shù)據(jù)時(shí)，可能需要從產(chǎn)品表、用戶表、用戶訂單表、以及訂單明細(xì)表中獲取相關(guān)的信息。

不過，今天我們要討論的是數(shù)據(jù)庫內(nèi)部如何利用算法實(shí)現(xiàn)連接查詢。通常實(shí)現(xiàn)連接查詢的算法有三種：Nested Loop Join、Hash Join 以及 Sort Merge Join。本文涉及到的數(shù)據(jù)庫包括 MySQL、Oracle、SQL Server、PostgreSQL 以及 SQLite，首先給出結(jié)論：

??關(guān)于各種內(nèi)、外連接的查詢方式和語法可以參考這篇文章。

接下來針對三種算法進(jìn)行具體的分析。
嵌套循環(huán)連接

嵌套循環(huán)連接（Nested Loop Join）是一種最基本的連接實(shí)現(xiàn)算法。它先從外部表（驅(qū)動表）中獲取滿足條件的數(shù)據(jù)，然后為每一行數(shù)據(jù)遍歷一次內(nèi)部表（被驅(qū)動表），獲取所有匹配的數(shù)據(jù)。下圖演示了嵌套循環(huán)連接的執(zhí)行過程（圖片來源于bertwagner）：

Nested Loop Join 類似于編程語言中的嵌套 for 循環(huán)；當(dāng)然，數(shù)據(jù)庫在實(shí)現(xiàn)時(shí)會進(jìn)行各種優(yōu)化，例如通過索引提高掃描速度。

我們可以通過執(zhí)行計(jì)劃查看 JOIN 的實(shí)現(xiàn)方式，先看 MySQL 中的以下示例（示例表來自這里）：

– MySQL
explain analyze
select e.first_name,e.last_name,e.salary,d.department_name
from employees e
join departments d on (e.department_id = d.department_id)
where d.department_name = ‘IT’;

-> Nested loop inner join (cost=7.38 rows=24) (actual time=0.080…0.102 rows=5 loops=1)
-> Filter: (d.department_name = ‘IT’) (cost=2.95 rows=3) (actual time=0.043…0.061 rows=1 loops=1)
-> Table scan on d (cost=2.95 rows=27) (actual time=0.036…0.050 rows=27 loops=1)
-> Index lookup on e using emp_department_ix (department_id=d.department_id) (cost=1.08 rows=9) (actual time=0.035…0.038 rows=5 loops=1)

對于以上查詢，MySQL 選擇了使用 Nested loop inner join 算法；departments 是驅(qū)動表，循環(huán) 1 次返回 1 行數(shù)據(jù)；employees 是被驅(qū)動表，使用索引進(jìn)行遍歷，然后回表查找表中的數(shù)據(jù)，循環(huán)了 1 次（因?yàn)?departments 返回了 1 條記錄）。實(shí)際上 MySQL 對這個(gè)嵌套循環(huán)連接進(jìn)行了優(yōu)化，采用的是 Index Nested Loop Join 算法，在內(nèi)層循環(huán)中掃描索引 emp_department_ix 而不是數(shù)據(jù)表，從而提高效率。

??關(guān)于各種數(shù)據(jù)庫中執(zhí)行計(jì)劃的查看方法，可以參考這篇文章。

下面是該語句在 Oracle 中的執(zhí)行計(jì)劃：

– Oracle
EXPLAIN PLAN FOR
select e.first_name,e.last_name,e.salary,d.department_name
from employees e
join departments d on (e.department_id = d.department_id)
where d.department_name = ‘IT’;

SELECT * FROM TABLE(DBMS_XPLAN.display);

--------------------------------------------------------------------------------------------------|
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time ||
--------------------------------------------------------------------------------------------------|
| 0 | SELECT STATEMENT | | 10 | 380 | 4 (0)| 00:00:01 ||
| 1 | NESTED LOOPS | | 10 | 380 | 4 (0)| 00:00:01 ||
| 2 | NESTED LOOPS | | 10 | 380 | 4 (0)| 00:00:01 ||
|* 3 | TABLE ACCESS FULL | DEPARTMENTS | 1 | 16 | 3 (0)| 00:00:01 ||
|* 4 | INDEX RANGE SCAN | EMP_DEPARTMENT_IX | 10 | | 0 (0)| 00:00:01 ||
| 5 | TABLE ACCESS BY INDEX ROWID| EMPLOYEES | 10 | 220 | 1 (0)| 00:00:01 ||
--------------------------------------------------------------------------------------------------|
|

3 - filter(“D”.“DEPARTMENT_NAME”=‘IT’) |
4 - access(“E”.“DEPARTMENT_ID”=“D”.“DEPARTMENT_ID”) |
|

Oracle 也是選擇了 departments 表作為，然后通過索引（EMP_DEPARTMENT_IX）范圍掃描進(jìn)行遍歷找出滿足連接條件的索引值和 ROWID，最后通過遍歷這些索引 ROWID 獲取 employees 中的數(shù)據(jù)。

SQL Server 的執(zhí)行計(jì)劃和 Oracle 幾乎完全一致：

– SQL Server
SET STATISTICS PROFILE ON
select e.first_name,e.last_name,e.salary,d.department_name
from employees e
join departments d on (e.department_id = d.department_id)
where d.department_name = ‘IT’;
SET STATISTICS PROFILE OFF

對于該語句，PostgreSQL 與其他數(shù)據(jù)庫的實(shí)現(xiàn)算法都不相同：

– PostgreSQL
explain analyze
select e.first_name,e.last_name,e.salary,d.department_name
from employees e
join departments d on (e.department_id = d.department_id)
where d.department_name = ‘IT’;

    Buckets: 1024  Batches: 1  Memory Usage: 9kB                                                              |
    ->  Seq Scan on departments d  (cost=0.00..1.34 rows=1 width=15) (actual time=0.016..0.028 rows=1 loops=1)|
          Filter: ((department_name)::text = 'IT'::text)                                                      |
          Rows Removed by Filter: 26                                                                          |

Planning Time: 0.502 ms |
Execution Time: 0.362 ms |

當(dāng)然，PostgreSQL 支持 Nested Loop Join，只是在這里它認(rèn)為 Hash Join 是更好的實(shí)現(xiàn)方式。關(guān)于 Hash Join 的介紹可以參考下文。

??如果我們使用set enable_hashjoin=off;禁用 PostgreSQL 中的哈希連接，可以看到以上示例的執(zhí)行計(jì)劃變成了嵌套循環(huán)連接。測試之后記得執(zhí)行set enable_hashjoin=on;啟用哈希連接。

最后是 SQLite 中的執(zhí)行計(jì)劃：

– SQLite
explain query plan
select e.first_name,e.last_name,e.salary,d.department_name
from employees e
join departments d on (e.department_id = d.department_id)
where d.department_name = ‘IT’;

SQLite 目前只實(shí)現(xiàn)了 Nested Loop Join，這里也是將 departments 選擇為驅(qū)動表。

對于驅(qū)動表返回少量數(shù)據(jù)集的情況，嵌套循環(huán)連接通?？梢垣@得很好的性能；如果被驅(qū)動表的連接字段上存在索引，性能會更好。

一般情況下，數(shù)據(jù)庫可以自行判斷哪個(gè)表作為驅(qū)動表；如果發(fā)現(xiàn)執(zhí)行計(jì)劃選擇了錯(cuò)誤的驅(qū)動表，首先應(yīng)該考慮統(tǒng)計(jì)信息是否正確；許多數(shù)據(jù)庫支持使用優(yōu)化器提示（hint）指定連接查詢中表的順序，建議謹(jǐn)慎使用。
哈希連接

哈希連接（Hash Join）使用其中一個(gè)表中滿足條件的記錄創(chuàng)建哈希表，然后掃描另一個(gè)表進(jìn)行匹配。哈希連接的執(zhí)行過程如下圖所示：

許多數(shù)據(jù)庫都支持哈希連接實(shí)現(xiàn)，MySQL 8.0.18 也加入了哈希連接，例如：

– MySQL
explain analyze
select e.first_name,e.last_name,e.salary,d.first_name
from employees e
join employees d on (e.salary = d.salary);
-> Inner hash join (d.salary = e.salary) (cost=1156.11 rows=1145) (actual time=0.582…1.006 rows=271 loops=1)
-> Table scan on d (cost=0.01 rows=107) (actual time=0.100…0.246 rows=107 loops=1)
-> Hash
-> Table scan on e (cost=10.95 rows=107) (actual time=0.199…0.271 rows=107 loops=1)

在上面的查詢中，我們使用 salary 字段連接兩個(gè) employees 表；由于該字段沒有索引，MySQL 選擇了 Inner hash join。通常來說，優(yōu)化器會選擇兩者中的小表或者數(shù)據(jù)源建立哈希表。

對于上面的示例，Oracle、SQL Server 以及 PostgreSQL 都選擇了哈希連接的方式；SQLite 不支持哈希連接，仍然使用嵌套循環(huán)連接。

哈希連接是執(zhí)行大數(shù)據(jù)集連接時(shí)的常用方式，但是它不支持范圍連接條件（t1.col < t2.col1）。對于哈希連接而言，不需要基于連接字段創(chuàng)建索引，因?yàn)樗粫盟饕M(jìn)行連接。當(dāng)然，為WHERE條件中的字段創(chuàng)建索引總是可以優(yōu)化性能。

哈希連接使用內(nèi)存構(gòu)建哈希表，但是如果數(shù)據(jù)量太大，需要使用磁盤臨時(shí)表。在SELECT中選擇更少的字段也可以提高哈希連接的性能，因?yàn)楣１碇写鎯α怂行枰淖侄巍?br> 排序合并連接

排序合并連接（Sort Merge Join）先將兩個(gè)數(shù)據(jù)源按照連接字段進(jìn)行排序（Sort），然后合并兩個(gè)已經(jīng)排序的集合，返回滿足連接條件的結(jié)果。排序合并連接的執(zhí)行過程如下圖所示：

以下是 Oracle 中的一個(gè)排序合并連接的示例：

– Oracle
EXPLAIN PLAN FOR
select e.first_name,e.last_name,e.salary,d.department_name
from employees e
join departments d on (e.department_id = d.department_id);

SELECT * FROM TABLE(DBMS_XPLAN.display);

--------------------------------------------------------------------------------------------|
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time ||
--------------------------------------------------------------------------------------------|
| 0 | SELECT STATEMENT | | 106 | 4028 | 6 (17)| 00:00:01 ||
| 1 | MERGE JOIN | | 106 | 4028 | 6 (17)| 00:00:01 ||
| 2 | TABLE ACCESS BY INDEX ROWID| DEPARTMENTS | 27 | 432 | 2 (0)| 00:00:01 ||
| 3 | INDEX FULL SCAN | DEPT_ID_PK | 27 | | 1 (0)| 00:00:01 ||
|* 4 | SORT JOIN | | 107 | 2354 | 4 (25)| 00:00:01 ||
| 5 | TABLE ACCESS FULL | EMPLOYEES | 107 | 2354 | 3 (0)| 00:00:01 ||
--------------------------------------------------------------------------------------------|
|

4 - access(“E”.“DEPARTMENT_ID”=“D”.“DEPARTMENT_ID”) |
filter(“E”.“DEPARTMENT_ID”=“D”.“DEPARTMENT_ID”) |

查詢首先按照索引 DEPT_ID_PK 的順序獲取 departments表中的數(shù)據(jù)，同時(shí)掃描 employees 表并且按照 department_id 列排序；然后依次比較合并這兩個(gè)數(shù)據(jù)集。

對于以上語句，并不是所有數(shù)據(jù)庫都會選擇排序合并連接；MySQL 和 SQLite 沒有實(shí)現(xiàn)排序合并連接，選擇的是嵌套循環(huán)連接；SQL Server 也選擇了嵌套循環(huán)連接，可以使用inner merge join強(qiáng)制使用排序合并連接；PostgreSQL 使用了哈希連接，可以使用set enable_hashjoin=off;禁用哈希連接，此時(shí)將會使用排序合并連接。

排序合并連接一般用在兩張表中沒有索引，并且數(shù)據(jù)已經(jīng)排好序的情況。雖然這種方式執(zhí)行速度很快，但大數(shù)情況下數(shù)據(jù)沒有排序，因此性能不如哈希連接。
總結(jié)

我們討論了數(shù)據(jù)庫實(shí)現(xiàn)連接查詢的三種算法：Nested Loop Join、Hash Join 以及 Sort Merge Join。了解這些算法的原理和優(yōu)缺點(diǎn)可以幫助我們優(yōu)化連接查詢語句的性能。