本文問題

1. 什么是外聯(lián)接，什么是內(nèi)聯(lián)接？
2. MySQL中的JOIN語法與標(biāo)準(zhǔn)SQL語法有什么不同？
3. MySQL Join算法有幾種？
4. NLJ算法的過程是怎樣的？
5. BNL算法的過程是怎樣的？

join語法

外聯(lián)接和內(nèi)聯(lián)接

• 內(nèi)聯(lián)接：INNER JOIN是內(nèi)聯(lián)接
  內(nèi)連接中，結(jié)果中只包括同時符合WHERE條件及ON條件的行
• 外聯(lián)接：LEFT JOIN和RIGHT JOIN都是外聯(lián)接
  外聯(lián)接中，T2中的行可以不符合ON條件，如果T2中的沒有符合ON條件的行，使用NULL代替T2中的列值

# 聯(lián)接條件使用`ON`表示
# 外聯(lián)接
SELECT * FROM T1 LEFT JOIN T2 ON T1.C1=T2.C2
# 內(nèi)聯(lián)接
SELECT * FROM T1 INNER JOIN T2 ON T1.C1=T2.C2

MySQL對JOIN語法的擴展

MySQL中，可以將多個表放在括號中，表示多表內(nèi)聯(lián)接：

SELECT * FROM t1 LEFT JOIN (t2, t3, t4)
                 ON (t2.a=t1.a AND t3.b=t1.b AND t4.c=t1.c)
# 等同與
SELECT * FROM t1 LEFT JOIN (t2 CROSS JOIN t3 CROSS JOIN t4)
                 ON (t2.a=t1.a AND t3.b=t1.b AND t4.c=t1.c)

在MySQL中，CROSS JOIN在語法上等同與INNER JOIN,他們可以互相替代。在標(biāo)準(zhǔn)SQL中，他們是不同的，INNER JOIN可以使用ON子句，CROSS JOIN不行。

Join算法

MySQL在表中執(zhí)行join聯(lián)結(jié)使用nested-loop算法或該算法的變體

• Nested-Loop Join(NLJ)
• Block Nested-Loop Join(BNL)

Nested-Loop Join算法

簡單的nested-loop join(NLJ)算法是一次將第一個表中的一行讀取到循環(huán)中，將每行放入到一個處理下一個join的表的嵌套循環(huán)中。如果仍有其他表加入，重復(fù)這個過程。
假設(shè)有一個在t1,t2,t3三個中的join操作，執(zhí)行以下類型的join：

Table   Join Type
t1      range
t2      ref
t3      ALL

如果使用簡單NLJ算法，join的過程如下：

for each row in t1 matching range {
  for each row in t2 matching reference key {
    for each row in t3 {
      if row satisfies join conditions, send to client
    }
  }
}

由于NLJ算法從外循環(huán)到內(nèi)循環(huán)處理行數(shù)據(jù)，通常會多次讀取內(nèi)循環(huán)中的表。

Block Nested-Loop Join算法

Block Nested-Loop(BNL)算法緩沖在外循環(huán)中讀取的行，來減少讀取內(nèi)循環(huán)表的次數(shù)。例如，如果將10行數(shù)據(jù)讀取到緩沖區(qū)中，然后將緩沖區(qū)傳入到內(nèi)循環(huán)，內(nèi)循環(huán)中讀取的行可以一次與緩沖區(qū)中的10行數(shù)據(jù)進(jìn)行對比，這可以減少讀取內(nèi)循環(huán)中的表的次數(shù)。

MySQL join緩沖區(qū)具有以下特征：

• 當(dāng)join類型為ALL或index，或者為range時，可以使用join緩沖區(qū)。緩沖區(qū)也可以應(yīng)用于外聯(lián)接。
• 即使類型為ALL或index，join buffer不會分配給非常量表。
• 只將join相關(guān)的列存儲到join buffer，不會將整行都存儲到join buffer中
• join_buffer_size決定了處理查詢時每個join buffer的大小
• 為每個可以被緩沖的join分配緩沖區(qū)，所以一個查詢在處理過程中可能會使用多個緩沖區(qū)
• 緩沖區(qū)在執(zhí)行join前分配，在查詢完成后釋放

對于之前NLJ算法的示例，如果使用join buffer，過程如下：

# 就是每當(dāng)join buffer滿后，對內(nèi)層的表進(jìn)行一次掃描并返回結(jié)果，然后清空join buffer。
# 由于數(shù)據(jù)量不一定會總是填滿join buffer。最后還要再檢查一次join buffer，如果不為空的話，再對內(nèi)層的表進(jìn)行一次掃描

for each row in t1 matching range {
  for each row in t2 matching reference key {
    store used columns from t1, t2 in join buffer
    if buffer is full {
      for each row in t3 {
        for each t1, t2 combination in join buffer {
          if row satisfies join conditions, send to client
        }
      }  # for each row in t3 循環(huán)結(jié)束
      empty join buffer
    } #if buffer is full 循環(huán)結(jié)束
  } # for each row in t2 循環(huán)結(jié)束
} # for each row in t1 循環(huán)結(jié)束

if buffer is not empty { 
  for each row in t3 {
    for each t1, t2 combination in join buffer {
      if row satisfies join conditions, send to client
    }
  }
}

S是存儲在緩沖區(qū)中的t1,t2組合大小，C是組合數(shù)量。掃描t3表的次數(shù)是:
(S * C)/join_buffer_size + 1
增加join_buffer_size可以降低t3的掃描次數(shù)，直到join_buffer_size足夠大，可以容納所有的行組合，在這種情況下，增加緩沖區(qū)不能繼續(xù)提升性能。

問題答案

1. 什么是外聯(lián)接，什么是內(nèi)聯(lián)接？

• 內(nèi)聯(lián)接：INNER JOIN是內(nèi)聯(lián)接
  內(nèi)連接中，結(jié)果中只包括同時符合WHERE條件及ON條件的行
• 外聯(lián)接：LEFT JOIN和RIGHT JOIN都是外聯(lián)接
  外聯(lián)接中，T2中的行可以不符合ON條件，如果T2中的沒有符合ON條件的行，使用NULL代替T2中的列值

2. MySQL中的JOIN語法與標(biāo)準(zhǔn)SQL語法有什么不同？

• MySQL可以將多個表放在括號中，表示多表內(nèi)聯(lián)接，如(T2,T3,T4)=(T2 CROSS JOIN T3 CROSS JOIN T3)。標(biāo)準(zhǔn)SQL不支持這么寫
• MySQL中的CROSS JOIN等同與INNER JOIN。標(biāo)準(zhǔn)SQL中，INNER JOIN可以包含ON條件，CROSS JOIN只能使用WHERE條件

3. MySQL Join算法有幾種？區(qū)別是什么？
   2種
   Nested-Loop Join算法，簡稱NLJ
Block Nested-Loop Join算法，簡稱BNL
BNL算法使用緩沖區(qū)緩存外層表的數(shù)據(jù)，以減少內(nèi)層表的循環(huán)查詢過程。
4. NLJ算法的過程是怎樣的？
   讀取第一個表中符合條件的行，將其放入到下層循環(huán)中，進(jìn)入下一層循環(huán)處理（檢查該行數(shù)據(jù)是否匹配其他條件），如果有其他要join的表，重復(fù)該過程。
5. BNL算法的過程是怎樣的？
   將第一個表中符合條件的行中于join相關(guān)的列放入到join buffer中
   當(dāng)join bufffer滿后，將join buffer放入下層循環(huán)中，進(jìn)入下一層循環(huán)處理（檢查join buffer中的行數(shù)據(jù)是否匹配其他條件），如果有其他要join的表，重復(fù)該過程。在循環(huán)中，返回匹配的行。
   處理結(jié)束后清空join buffer，對第一個表繼續(xù)進(jìn)行循環(huán)
   循環(huán)結(jié)束后，檢查join buffer是否為空，如果join buffer不為空，檢查join buffer中的行數(shù)據(jù)是否匹配其他條件。