相関サブクエリとパフォーマンス

なぜこの記事を書いたのか

業務内で相関サブクエリで書かれていたスロウクエリを改善したところ、最近入社された方から「相関サブクエリってはじめて聞きました」ということだったので簡単な解説をすることになった。
これはその資料である（アバンタイトル感

TL;DR

相関サブクエリってあんまりパフォーマンス良くないよね（実行計画を確認したときにコストが高いよね）。
取得したいデータにもよるけど相関サブクエリ以外の書き方でも取得できるよ！
長々書いてあるけど鵜呑みにせずに、実行計画を確認しよう！！（ここが一番大事

環境

・PostgreSQL 9.6.18

説明用のテーブル構成とデータ件数

-- 企業テーブル
CREATE TABLE companies (
id SERIAL PRIMARY KEY,
name varchar(255) NOT NULL, -- 企業名
is_listed boolean NOT NULL DEFAULT false -- 上場済みフラグ
);

-- 従業員テーブル
CREATE TABLE employees (
id SERIAL PRIMARY KEY,
company_id int references companies(id) NOT NULL, -- 企業テーブルid
name varchar(255) -- 名前
);

SELECT count(*) FROM companies;
 count
-------
   120
(1 行)

SELECT count(*) FROM employees;
 count
--------
 240000
(1 行)

今回はパーティションを切ってない状態でSQLを流しています。

相関サブクエリってどんなの？

非上場企業に所属する従業員数を取得する為のクエリは以下のように記述します。

-- 相関サブクエリの例
SELECT count(*)
FROM employees  
WHERE (
  SELECT is_listed
  FROM companies 
  WHERE id = employees.company_id 
) IS FALSE;

相関となる部分が WHERE id = employees.company_id の部分になります。
外側の従業員テーブルの一行毎に、WHERE句に記述されたサブクエリが実行されます。

上のSQLを非相関サブクエリで記述すると以下のようになります。

-- 非相関サブクエリの例
SELECT count(*)
FROM employees  
WHERE company_id IN (
  SELECT id 
  FROM companies 
  WHERE is_listed IS FALSE  
);

実際どれくらいパフォーマンスが違うのか

\timing
タイミングは on です。

-- 相関サブクエリの例
SELECT count(*)
FROM employees  
WHERE (
  SELECT is_listed
  FROM companies 
  WHERE id = employees.company_id 
) IS FALSE;

 count
--------
 120000
(1 行)

時間: 3090.592 ms


-- 非相関サブクエリの例
SELECT count(*)
FROM employees  
WHERE company_id IN (
  SELECT id 
  FROM companies 
  WHERE is_listed IS FALSE  
);

 count
--------
 120000
(1 行)

時間: 46.497 ms

\timing で実行速度を計測できます。
相関サブクエリでは、約3秒ほどかかったのに対して非相関サブクエリの方では約0.05秒でした。
今回の結果だけで言えば、60倍近くの差になります。

次は、実行計画を確認してみます。
確認方法は先程のクエリの頭に EXPLAIN をつけると確認できます。

-- 相関サブクエリの例
EXPLAIN
SELECT count(*)
FROM employees  
WHERE (
  SELECT is_listed
  FROM companies 
  WHERE id = employees.company_id 
) IS FALSE;

                              QUERY PLAN
-------------------------------------------------------------------------
 Aggregate  (cost=604380.00..604380.01 rows=1 width=8)
   ->  Seq Scan on employees  (cost=0.00..604080.00 rows=120000 width=0)
         Filter: ((SubPlan 1) IS FALSE)
         SubPlan 1
           ->  Seq Scan on companies  (cost=0.00..2.50 rows=1 width=1)
                 Filter: (id = employees.company_id)
(6 行)


-- 非相関サブクエリの例
EXPLAIN
SELECT count(*)
FROM employees  
WHERE company_id IN (
  SELECT id 
  FROM companies 
  WHERE is_listed IS FALSE  
);

                                 QUERY PLAN
-----------------------------------------------------------------------------
 Aggregate  (cost=6347.95..6347.96 rows=1 width=8)
   ->  Hash Semi Join  (cost=2.95..6047.95 rows=120000 width=0)
         Hash Cond: (employees.company_id = companies.id)
         ->  Seq Scan on employees  (cost=0.00..4080.00 rows=240000 width=4)
         ->  Hash  (cost=2.20..2.20 rows=60 width=4)
               ->  Seq Scan on companies  (cost=0.00..2.20 rows=60 width=4)
                     Filter: (is_listed IS FALSE)
(7 行)

相関サブクエリの方は、 Filter: ((SubPlan 1) IS FALSE) で１行毎に SubPlan 1 が実行されているのが分かります。

非相関サブクエリの方は、 Seq Scan on companies > Filter: (is_listed IS FALSE) の結果をHashテーブルに格納しています。
Hash Cond: (employees.company_id = companies.id) でHashテーブルとemployeesテーブル結合しているので、相関サブクエリと比較した際に実行速度に差が生まれています。
実行計画のコストを見ても相関サブクエリの最終コスト604380.01に対して非相関サブクエリは6347.96で大きく差があるのが分かります。

それじゃあEXISTSって使わない方がいいの？

結果から述べるとEXISTSを使っても問題ありません。
EXISTSを使った存在確認のクエリーは以下のように記述します。

SELECT count(*)
FROM employees  
WHERE EXISTS (
  SELECT 1
  FROM companies 
  WHERE id = employees.company_id
  AND is_listed IS FALSE
);

 count
--------
 120000
(1 行)

時間: 43.455 ms

WHERE id = employees.company_id の部分があるのに実行速度が約0.04秒で非相関サブクエリと同程度になりました。

先程のクエリの実行計画を確認してみます。

EXPLAIN
SELECT count(*)
FROM employees  
WHERE EXISTS (
  SELECT 1
  FROM companies 
  WHERE id = employees.company_id
  AND is_listed IS FALSE
);

                                 QUERY PLAN
-----------------------------------------------------------------------------
 Aggregate  (cost=6347.95..6347.96 rows=1 width=8)
   ->  Hash Semi Join  (cost=2.95..6047.95 rows=120000 width=0)
         Hash Cond: (employees.company_id = companies.id)
         ->  Seq Scan on employees  (cost=0.00..4080.00 rows=240000 width=4)
         ->  Hash  (cost=2.20..2.20 rows=60 width=4)
               ->  Seq Scan on companies  (cost=0.00..2.20 rows=60 width=4)
                     Filter: (is_listed IS FALSE)
(7 行)

非相関サブクエリと同じようにHashテーブルを使用してテーブル結合するように変わりました。
なので、EXISTSを使用しても実行時間の遅延は発生しません。

相関サブクエリを非相関サブクエリに置き換える

相関サブクエリを避けることで実行速度が改善する場合もあるので一例として参考にしてみてください。
EXPLAINはクエリの頭につけるだけなのでクエリを省略しています。

SELECT
  name,
  (
    SELECT count(*)
    FROM employees
    WHERE company_id = companies.id
  ) AS employees_count
FROM companies
ORDER BY id;

        name        | employees_count
--------------------+-----------------
 佐々木運輸合同会社 |            2000
 ...以下続く
 合資会社原水産     |            2000
(120 行)

時間: 3248.351 ms

                                       QUERY PLAN
----------------------------------------------------------------------------------------
 Index Scan using companies_pkey on companies  (cost=0.14..562215.14 rows=120 width=36)
   SubPlan 1
     ->  Aggregate  (cost=4685.00..4685.01 rows=1 width=8)
           ->  Seq Scan on employees  (cost=0.00..4680.00 rows=2000 width=0)
                 Filter: (company_id = companies.id)
(5 行)


-- 書き換え
SELECT
  name,
  coalesce(employees_count, 0)
FROM companies
LEFT JOIN (
  SELECT
    company_id,
    count(*) AS employees_count
  FROM employees
  GROUP BY company_id 
) AS sub
  ON companies.id = sub.company_id
ORDER BY id;

        name        | employees_count
--------------------+-----------------
 佐々木運輸合同会社 |            2000
  ...以下続く
 合資会社原水産     |            2000
(120 行)

時間: 52.071 ms

                                       QUERY PLAN
-----------------------------------------------------------------------------------------
 Merge Left Join  (cost=5292.89..5295.29 rows=120 width=36)
   Merge Cond: (companies.id = sub.company_id)
   ->  Sort  (cost=6.34..6.64 rows=120 width=28)
         Sort Key: companies.id
         ->  Seq Scan on companies  (cost=0.00..2.20 rows=120 width=28)
   ->  Sort  (cost=5286.54..5286.84 rows=120 width=12)
         Sort Key: sub.company_id
         ->  Subquery Scan on sub  (cost=5280.00..5282.40 rows=120 width=12)
               ->  HashAggregate  (cost=5280.00..5281.20 rows=120 width=12)
                     Group Key: employees.company_id
                     ->  Seq Scan on employees  (cost=0.00..4080.00 rows=240000 width=4)
(11 行)

上記の書き換えのコツとしては、サブクエリ内でcompany_id毎に集計を行い、LEFT JOINで外部結合する事で従業員テーブルに1件もレコードが存在しない企業も結果含まれるようにする事と、employees_count が null を返すので coalesce で 0 に置き換える事です。

相関サブクエリの使い所

良い例がなかなか思いつかなかったですが、以下のようなものを一例として参考にしてみてください。
内容としては、自社を除いた全企業の平均従業員数を超えた企業のみを抽出するというクエリです。

SELECT 
  companies.name,
  employees_count
FROM companies
LEFT JOIN (
  SELECT
    company_id,
    count(*) AS employees_count
  FROM employees
  GROUP BY company_id 
) AS sub
  ON companies.id = sub.company_id
WHERE employees_count > (
  SELECT avg(count)
  FROM (
	  SELECT count(*) AS count
	  FROM employees
	  WHERE company_id <> companies.id
	  GROUP BY company_id
  ) AS count_by_company
);

       name       | employees_count
------------------+-----------------
 合同会社松井印刷 |            2001
 坂本運輸株式会社 |            2003
 株式会社中山保険 |            2002
(3 行)

時間: 7498.667 ms

                                           QUERY PLAN
-------------------------------------------------------------------------------------------------
 Hash Join  (cost=5283.70..710013.85 rows=40 width=32)
   Hash Cond: (employees.company_id = companies.id)
   Join Filter: (((count(*)))::numeric > (SubPlan 1))
   ->  HashAggregate  (cost=5280.00..5281.20 rows=120 width=12)
         Group Key: employees.company_id
         ->  Seq Scan on employees  (cost=0.00..4080.00 rows=240000 width=4)
   ->  Hash  (cost=2.20..2.20 rows=120 width=28)
         ->  Seq Scan on companies  (cost=0.00..2.20 rows=120 width=28)
   SubPlan 1
     ->  Aggregate  (cost=5872.70..5872.71 rows=1 width=32)
           ->  HashAggregate  (cost=5870.00..5871.20 rows=120 width=12)
                 Group Key: employees_1.company_id
                 ->  Seq Scan on employees employees_1  (cost=0.00..4680.00 rows=238000 width=4)
                       Filter: (company_id <> companies.id)
(14 行)

まとめ

PostgreSQLのバージョンや、他のDBMSだと挙動が異なる可能性があります。
今回の内容を参考程度に留めておいて、実行計画を確認しながらSQLを組みてていくと効率の良い（コストが低い）クエリを書けると思います。
気になったらぜひ確認してみてください！