LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@yosukenaruse

PostgreSQLの結合アルゴリズム完全ガイド：ネステッドループ、ハッシュ結合、マージ結合

Posted at

PostgreSQLの結合アルゴリズム完全ガイド：ネステッドループ、ハッシュ結合、マージ結合

はじめに

PostgreSQLのクエリオプティマイザは、テーブル間の結合を実行する際に、複数の結合アルゴリズムから最適なものを選択します。この記事では、PostgreSQLで使用される主要な結合アルゴリズム（ネステッドループ結合、ハッシュ結合、マージ結合）の仕組みと特徴を詳しく解説します。

結合アルゴリズムの概要

PostgreSQLでは以下の3つの主要な結合アルゴリズムが使用されます：

  1. ネステッドループ結合（Nested Loop Join）
  2. ハッシュ結合（Hash Join）
  3. マージ結合（Merge Join）

各アルゴリズムには特徴があり、データサイズ、インデックスの有無、ソート状態などによって最適なものが選択されます。

1. ネステッドループ結合（Nested Loop Join）

基本的な仕組み

ネステッドループ結合は、最もシンプルな結合アルゴリズムです。外側のテーブル（駆動表）の各行に対して、内側のテーブル（被駆動表）を全件スキャンして結合条件に一致する行を探します。

-- サンプルテーブル
CREATE TABLE employees (
    id INTEGER PRIMARY KEY,
    name VARCHAR(100),
    department_id INTEGER
);

CREATE TABLE departments (
    id INTEGER PRIMARY KEY,
    name VARCHAR(100)
);

INSERT INTO employees VALUES
(1, '田中', 1),
(2, '佐藤', 1),
(3, '鈴木', 2),
(4, '高橋', 2),
(5, '渡辺', 3);

INSERT INTO departments VALUES
(1, '営業部'),
(2, '開発部'),
(3, '人事部');

ネステッドループ結合の実行例

EXPLAIN (ANALYZE, BUFFERS) 
SELECT e.name, d.name 
FROM employees e 
JOIN departments d ON e.department_id = d.id;

実行計画例：

Nested Loop  (cost=0.00..0.11 rows=5 width=64) (actual time=0.008..0.012 rows=5 loops=1)
  ->  Seq Scan on employees e  (cost=0.00..0.05 rows=5 width=36) (actual time=0.003..0.004 rows=5 loops=1)
  ->  Index Scan using departments_pkey on departments d  (cost=0.00..0.01 rows=1 width=28) (actual time=0.001..0.001 rows=1 loops=5)
        Index Cond: (id = e.department_id)

ネステッドループ結合の特徴

利点：

  • 実装がシンプル
  • メモリ使用量が少ない
  • 内側テーブルにインデックスがある場合、効率的

欠点：

  • 内側テーブルが大きい場合、パフォーマンスが悪い
  • 時間計算量：O(n × m)（n: 外側テーブル行数、m: 内側テーブル行数）

最適化されたネステッドループ結合

-- インデックスを作成してネステッドループ結合を最適化
CREATE INDEX idx_employees_department_id ON employees(department_id);

EXPLAIN (ANALYZE, BUFFERS) 
SELECT e.name, d.name 
FROM employees e 
JOIN departments d ON e.department_id = d.id;

2. ハッシュ結合（Hash Join）

基本的な仕組み

ハッシュ結合は、結合キーをハッシュ関数でハッシュ値に変換し、ハッシュテーブルを使用して結合を実行します。

  1. 構築フェーズ: 小さいテーブル（構築表）の結合キーをハッシュテーブルに格納
  2. プローブフェーズ: 大きいテーブル（プローブ表）の各行の結合キーをハッシュして、ハッシュテーブルから一致する行を検索

ハッシュ結合の実行例

-- 大きなテーブルを作成
CREATE TABLE large_orders (
    id INTEGER PRIMARY KEY,
    customer_id INTEGER,
    order_date DATE,
    amount DECIMAL(10,2)
);

CREATE TABLE customers (
    id INTEGER PRIMARY KEY,
    name VARCHAR(100),
    email VARCHAR(100)
);

-- データを挿入（実際の環境ではより多くのデータ）
INSERT INTO large_orders SELECT 
    generate_series(1, 10000),
    (random() * 1000)::integer,
    '2024-01-01'::date + (random() * 365)::integer,
    (random() * 10000)::decimal(10,2);

INSERT INTO customers SELECT 
    generate_series(1, 1000),
    'Customer ' || generate_series(1, 1000),
    'customer' || generate_series(1, 1000) || '@example.com';

EXPLAIN (ANALYZE, BUFFERS) 
SELECT c.name, COUNT(*), SUM(o.amount)
FROM large_orders o 
JOIN customers c ON o.customer_id = c.id
GROUP BY c.id, c.name;

実行計画例：

HashAggregate  (cost=... rows=1000 width=...)
  Group Key: c.id, c.name
  ->  Hash Join  (cost=... rows=10000 width=...)
        Hash Cond: (o.customer_id = c.id)
        ->  Seq Scan on large_orders o  (cost=... rows=10000 width=...)
        ->  Hash  (cost=... rows=1000 width=...)
              ->  Seq Scan on customers c  (cost=... rows=1000 width=...)

ハッシュ結合の特徴

利点：

  • 大きなテーブル間の結合に効率的
  • インデックスが不要
  • 時間計算量：O(n + m)（最良の場合）

欠点：

  • メモリ使用量が多い
  • ハッシュテーブルの構築に時間がかかる
  • ハッシュ衝突の可能性

ハッシュ結合の最適化

-- 結合キーにインデックスを作成（ハッシュ結合の効率化）
CREATE INDEX idx_large_orders_customer_id ON large_orders(customer_id);

-- 統計情報を更新
ANALYZE large_orders;
ANALYZE customers;

3. マージ結合（Merge Join）

基本的な仕組み

マージ結合は、両方のテーブルを結合キーでソートし、順次比較して結合を実行します。

  1. ソートフェーズ: 両テーブルを結合キーでソート
  2. マージフェーズ: ソートされたデータを順次比較して結合

マージ結合の実行例

-- ソート済みデータの例
CREATE TABLE sorted_orders (
    id INTEGER PRIMARY KEY,
    customer_id INTEGER,
    order_date DATE,
    amount DECIMAL(10,2)
);

CREATE TABLE sorted_customers (
    id INTEGER PRIMARY KEY,
    name VARCHAR(100),
    email VARCHAR(100)
);

-- データを挿入（customer_idでソート済み）
INSERT INTO sorted_orders SELECT 
    generate_series(1, 10000),
    (generate_series(1, 10000) % 1000) + 1,
    '2024-01-01'::date + (random() * 365)::integer,
    (random() * 10000)::decimal(10,2);

INSERT INTO sorted_customers SELECT 
    generate_series(1, 1000),
    'Customer ' || generate_series(1, 1000),
    'customer' || generate_series(1, 1000) || '@example.com';

EXPLAIN (ANALYZE, BUFFERS) 
SELECT c.name, COUNT(*), SUM(o.amount)
FROM sorted_orders o 
JOIN sorted_customers c ON o.customer_id = c.id
GROUP BY c.id, c.name;

実行計画例：

HashAggregate  (cost=... rows=1000 width=...)
  Group Key: c.id, c.name
  ->  Merge Join  (cost=... rows=10000 width=...)
        Merge Cond: (o.customer_id = c.id)
        ->  Sort  (cost=... rows=10000 width=...)
              Sort Key: o.customer_id
              ->  Seq Scan on sorted_orders o  (cost=... rows=10000 width=...)
        ->  Sort  (cost=... rows=1000 width=...)
              Sort Key: c.id
              ->  Seq Scan on sorted_customers c  (cost=... rows=1000 width=...)

マージ結合の特徴

利点：

  • 大きなテーブル間の結合に効率的
  • メモリ使用量が比較的少ない
  • 時間計算量：O(n log n + m log m)（ソートを含む）

欠点：

  • 事前にソートが必要
  • ソートのコストが高い場合がある

マージ結合の最適化

-- 結合キーにインデックスを作成（ソートを回避）
CREATE INDEX idx_sorted_orders_customer_id ON sorted_orders(customer_id);
CREATE INDEX idx_sorted_customers_id ON sorted_customers(id);

-- 統計情報を更新
ANALYZE sorted_orders;
ANALYZE sorted_customers;

結合アルゴリズムの選択基準

PostgreSQLの選択ロジック

PostgreSQLのクエリオプティマイザは以下の要因を考慮して結合アルゴリズムを選択します：

  1. テーブルサイズ
  2. インデックスの有無
  3. データのソート状態
  4. メモリ使用量
  5. 結合条件の複雑さ

各アルゴリズムの適用場面

ネステッドループ結合が選択される場合

  • 内側テーブルが小さい
  • 内側テーブルに適切なインデックスがある
  • 結合条件が複雑
-- ネステッドループ結合が選択される例
EXPLAIN 
SELECT e.name, d.name 
FROM employees e 
JOIN departments d ON e.department_id = d.id 
WHERE e.name LIKE '田中%';

ハッシュ結合が選択される場合

  • 両テーブルが大きい
  • インデックスがない
  • 等価結合
-- ハッシュ結合が選択される例
EXPLAIN 
SELECT o.customer_id, c.name, COUNT(*)
FROM large_orders o 
JOIN customers c ON o.customer_id = c.id
GROUP BY o.customer_id, c.name;

マージ結合が選択される場合

  • 両テーブルが大きい
  • 結合キーでソート済みまたはインデックスがある
  • 範囲結合
-- マージ結合が選択される例
EXPLAIN 
SELECT o.customer_id, c.name
FROM sorted_orders o 
JOIN sorted_customers c ON o.customer_id = c.id
WHERE o.order_date BETWEEN '2024-01-01' AND '2024-12-31';

結合アルゴリズムのパフォーマンス比較

実行時間の比較

-- パフォーマンステスト用のクエリ
\timing on

-- ネステッドループ結合
SELECT COUNT(*) FROM employees e JOIN departments d ON e.department_id = d.id;

-- ハッシュ結合
SELECT COUNT(*) FROM large_orders o JOIN customers c ON o.customer_id = c.id;

-- マージ結合
SELECT COUNT(*) FROM sorted_orders o JOIN sorted_customers c ON o.customer_id = c.id;

\timing off

メモリ使用量の比較

-- メモリ使用量を確認
EXPLAIN (ANALYZE, BUFFERS, VERBOSE) 
SELECT c.name, COUNT(*), SUM(o.amount)
FROM large_orders o 
JOIN customers c ON o.customer_id = c.id
GROUP BY c.id, c.name;

結合アルゴリズムの最適化テクニック

1. インデックスの最適化

-- 結合キーに適切なインデックスを作成
CREATE INDEX idx_orders_customer_id ON large_orders(customer_id);
CREATE INDEX idx_customers_id ON customers(id);

-- 複合インデックスの活用
CREATE INDEX idx_orders_customer_date ON large_orders(customer_id, order_date);

2. 統計情報の更新

-- 統計情報を定期的に更新
ANALYZE large_orders;
ANALYZE customers;
ANALYZE employees;
ANALYZE departments;

3. クエリの書き方の最適化

-- 効率的な結合順序
SELECT c.name, COUNT(*)
FROM customers c
JOIN large_orders o ON c.id = o.customer_id
WHERE o.order_date >= '2024-01-01'
GROUP BY c.id, c.name;

-- 非効率的な結合順序（避けるべき）
SELECT c.name, COUNT(*)
FROM large_orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.order_date >= '2024-01-01'
GROUP BY c.id, c.name;

4. 結合ヒントの使用

-- PostgreSQLでは結合ヒントは直接サポートされていないが、
-- クエリの書き方で影響を与えることができる

-- ネステッドループ結合を促す
SELECT /*+ NESTED_LOOP(e d) */ e.name, d.name
FROM employees e 
JOIN departments d ON e.department_id = d.id;

実際の運用での注意点

1. 実行計画の監視

-- 実行計画を定期的に確認
EXPLAIN (ANALYZE, BUFFERS) 
SELECT c.name, COUNT(*), SUM(o.amount)
FROM large_orders o 
JOIN customers c ON o.customer_id = c.id
GROUP BY c.id, c.name;

2. パフォーマンスの監視

-- スロークエリの特定
SELECT query, mean_time, calls
FROM pg_stat_statements
WHERE mean_time > 1000
ORDER BY mean_time DESC;

3. メモリ設定の最適化

-- 重要な設定パラメータ
SHOW work_mem;        -- ソートやハッシュ操作のメモリ
SHOW shared_buffers;  -- 共有バッファサイズ
SHOW effective_cache_size; -- 有効キャッシュサイズ

まとめ

PostgreSQLの結合アルゴリズムは、データの特性とクエリの要件に応じて最適なものが選択されます。

主要なポイント

  1. ネステッドループ結合: 小さいテーブルとインデックスがある場合に効率的
  2. ハッシュ結合: 大きなテーブル間の等価結合に最適
  3. マージ結合: ソート済みデータや範囲結合に適している

最適化のベストプラクティス

  1. 適切なインデックスの作成
  2. 統計情報の定期的な更新
  3. 実行計画の監視
  4. メモリ設定の最適化

これらのアルゴリズムを理解し、適切に最適化することで、PostgreSQLの結合パフォーマンスを大幅に向上させることができます。

参考資料

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?