巢狀迴圈 • SQL 效能解密

巢狀迴圈 join（nested loops join）是最基本的 join 演算法。它的運作方式就像兩個巢狀查詢：

外層（驅動）查詢從一張表取出結果。
對驅動查詢的每一列，再執行第二個查詢從另一張表取出對應資料。

N+1 選取問題#

你其實可以用「巢狀 select」自己實作巢狀迴圈演算法。但這是個麻煩的做法——網路延遲會疊加在磁碟延遲之上，讓整體回應時間更糟。

儘管如此，「巢狀 select」依然非常常見，因為它太容易在不知不覺中被寫出來。物件關聯對映（ORM, object-relational mapping）工具在這方面尤其「幫忙」——以至於所謂的 N+1 選取問題在業界惡名昭彰。

之所以叫 N+1 問題，是因為當驅動查詢回傳 N 列時，總共會執行 N+1 次 select。

以「搜尋姓氏以 WIN 開頭的員工，並抓取他們所有的銷售記錄」為例，多數 ORM 不會產生 SQL join，而是用巢狀 select 去查 SALES 表。

各 ORM 產生 N+1 查詢的實例

Java（JPA CriteriaBuilder）

CriteriaBuilder queryBuilder = em.getCriteriaBuilder();
CriteriaQuery<Employees>
     query = queryBuilder.createQuery(Employees.class);
Root<Employees> r = query.from(Employees.class);
query.where(
   queryBuilder.like(
      queryBuilder.upper(r.get(Employees_.lastName)),
      "WIN%"
   )
);

List<Employees> emp = em.createQuery(query).getResultList();
for (Employees e: emp) {
  // process Employee
  for (Sales s: e.getSales()) {
    // process sale for Employee
  }
}

Hibernate JPA 3.6.0 產生 N+1 個查詢：

select employees0_.subsidiary_id as subsidiary1_0_
       -- MORE COLUMNS
  from employees employees0_
 where upper(employees0_.last_name) like ?

   select sales0_.subsidiary_id as subsidiary4_0_1_
     from sales sales0_
    where sales0_.subsidiary_id=?
      and sales0_.employee_id=?

   select sales0_.subsidiary_id as subsidiary4_0_1_
     from sales sales0_
    where sales0_.subsidiary_id=?
      and sales0_.employee_id=?

Perl（DBIx::Class）

my @employees =
   $schema->resultset('Employees')
          ->search({'UPPER(last_name)' => {-like=>'WIN%'}});

foreach my $employee (@employees) {
   # process Employee
   foreach my $sale ($employee->sales) {
      # process Sale for Employee
   }
}

PHP（Doctrine query builder）

$qb = $em->createQueryBuilder();
$qb->select('e')
   ->from('Employees', 'e')
   ->where("upper(e.last_name) like :last_name")
   ->setParameter('last_name', 'WIN%');
$r = $qb->getQuery()->getResult();
foreach ($r as $row) {
   // process Employee
   foreach ($row->getSales() as $sale) {
      // process Sale for Employee
   }
}

三者都產生同樣形態的 N+1 查詢。

實務：開啟 SQL logging

DBIx::Class：在 shell 中 export DBIC_TRACE=1。
Doctrine：只能在原始碼層級設定——別忘了在正式環境關掉。考慮自建可設定的 logger。
```
$logger = new \Doctrine\DBAL\Logging\EchoSqlLogger;
$config->setSQLLogger($logger);
```
Hibernate（原生）：在 App.config 或 hibernate.cfg.xml 中設 <property name="show_sql">true</property>。

JPA：在 persistence.xml 中，依 provider 而異：

<property name="eclipselink.logging.level" value="FINE"/>
<property name="hibernate.show_sql" value="TRUE"/>
<property name="openjpa.Log" value="SQL=TRACE"/>

多數 ORM 也提供程式化開啟的方式，但那有不小心把設定部署到正式環境的風險。

為巢狀迴圈 join 建索引#

「巢狀 select」雖是反模式，卻把巢狀迴圈 join 解釋得很好——資料庫執行 join 的方式，正如上面那些 ORM 所做的。因此為巢狀迴圈 join 建索引，就等同於為那些 select 敘述建索引：

CREATE INDEX emp_up_name ON employees (UPPER(last_name));
CREATE INDEX sales_emp   ON sales (subsidiary_id, employee_id);

為什麼 SQL join 仍勝過巢狀 select#

即使兩者執行完全相同的索引查找，SQL join 依然更有效率——因為它避免了大量網路往返。就算 join 傳輸的資料總量更大（每筆銷售都重複帶上員工屬性），它仍然更快。

原因回到效能的兩個維度：回應時間與吞吐量——在電腦網路中稱為延遲與頻寬。

頻寬對回應時間影響輕微，延遲的影響則極為巨大。這代表：資料庫往返次數對回應時間的影響，比傳輸資料量更重要。

掌控 ORM 的 join 行為#

多數 ORM 都提供產生 SQL join 的方式，其中最重要的大概是所謂的積極抓取模式（eager fetching）。它通常在實體對映的屬性層級設定——例如 Sales 類別中的 employees 屬性；設定後，ORM 每次存取 SALES 表時都會 join EMPLOYEES 表。

若你並非每次存取父物件都需要子記錄，eager fetching 反而有害：電話簿應用在顯示員工細節時，根本沒必要載入 SALES 記錄。其他情境可能需要，但不是每次都需要——靜態設定不是解法。

要達到最佳效能，你必須完全掌控 join，也就是在執行期控制 join 行為。

各語言在執行期控制 join 的寫法

Java（JPA）

JPA 的 CriteriaBuilder 提供 Root<>.fetch() 方法控制 join。下例用 left join 取回所有員工（即使有些人沒有銷售記錄）：

CriteriaBuilder qb = em.getCriteriaBuilder();
CriteriaQuery<Employees> q = qb.createQuery(Employees.class);
Root<Employees> r = q.from(Employees.class);
q.where(queryBuilder.like(
    queryBuilder.upper(r.get(Employees_.lastName)),
    "WIN%")
);
r.fetch("sales", JoinType.LEFT);
// 避免 Employee 記錄重複
query.distinct(true);
List<Employees> emp = em.createQuery(query).getResultList();

JPA 與 Hibernate 會為每一筆銷售回傳一次員工——有 30 筆銷售的員工會出現 30 次。這雖然很擾人，卻是規格所定義的行為（EJB 3.0 persistency，4.4.5.3「Fetch Joins」）。你可以手動去重，或如上例使用 distinct()。

Hibernate 3.6.0 產生的 SQL 帶有預期的 left join，但也帶了不必要的 distinct：

select distinct
       employees0_.subsidiary_id as subsidiary1_0_0_
     , sales1_.sale_id as sale1_0__
  from employees employees0_
  left outer join sales sales1_
          on employees0_.subsidiary_id=sales1_.subsidiary_id
         and employees0_.employee_id=sales1_.employee_id
 where upper(employees0_.last_name) like ?

可惜 JPA 沒有提供「只去重父實體、不去重子記錄」的獨立 API。SQL 中的 distinct 令人警惕，因為多數資料庫真的會去過濾重複記錄——只有少數資料庫能認出主鍵本來就保證了唯一性。

Hibernate 的原生 API 則改在客戶端用 result set transformer 解決：

Criteria c = session.createCriteria(Employees.class);
c.add(Restrictions.ilike("lastName", "Win%"));
c.setFetchMode("sales", FetchMode.JOIN);
c.setResultTransformer(Criteria.DISTINCT_ROOT_ENTITY);
List<Employees> result = c.list();

這產生了乾淨、沒有多餘子句的 SQL。注意 Hibernate 用 lower() 做大小寫不敏感查詢——這對函式索引是重要細節。

Perl（DBIx::Class）

my @employees =
   $schema->resultset('Employees')
          ->search({ 'UPPER(last_name)' => {-like => 'WIN%'}
                   , {prefetch => ['sales']}
                   });

產生的 SQL 帶有 LEFT JOIN，但也多了一個應用程式並未要求的 ORDER BY——資料庫必須據此排序結果集，那可能要花上一段時間。

PHP（Doctrine）

$qb = $em->createQueryBuilder();
$qb->select('e,s')
   ->from('Employees', 'e')
   ->leftJoin('e.sales', 's')
   ->where("upper(e.last_name) like :last_name")
   ->setParameter('last_name', 'WIN%');
$r = $qb->getQuery()->getResult();

產生乾淨的 LEFT JOIN SQL。

執行計畫#

---------------------------------------------------------------
|Id |Operation                    | Name        | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT             |             |  822 |   38 |
| 1 | NESTED LOOPS OUTER          |             |  822 |   38 |
| 2 |  TABLE ACCESS BY INDEX ROWID| EMPLOYEES   |    1 |    4 |
|*3 |   INDEX RANGE SCAN          | EMP_UP_NAME |    1 |      |
| 4 |  TABLE ACCESS BY INDEX ROWID| SALES       |  821 |   34 |
|*5 |   INDEX RANGE SCAN          | SALES_EMP   |   31 |      |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
  3 - access(UPPER("LAST_NAME") LIKE 'WIN%')
      filter(UPPER("LAST_NAME") LIKE 'WIN%')
  5 - access("E0_"."SUBSIDIARY_ID"="S1_"."SUBSIDIARY_ID"(+)
        AND "E0_"."EMPLOYEE_ID" ="S1_"."EMPLOYEE_ID"(+))

資料庫先透過 EMP_UP_NAME 從 EMPLOYEES 取得結果，再為每位員工抓取 SALES 中的對應記錄。

當驅動查詢回傳的結果集很小時，巢狀迴圈 join 有很好的效能。否則最佳化工具可能改選完全不同的演算法——例如下一節的雜湊 join。但這只有在應用程式真的用 join 告訴資料庫它需要什麼資料時才可能發生。