MySQL8.0の時代になって久しいこの頃、今年のMySQL SummitのKeynoteで、マネージドサービス(HeatWave)でのみ利用可能だったハイパーグラフオプティマイザが、そろそろオンプレミスでも一般提供されるようになるかも？とWim Coekaertsからアナウンスされました。また開発チームから紹介するセッションもありました。

ハイパーグラフオプティマイザのざっくり解説

従来のMySQLオプティマイザは、基本的にテーブルの結合順序を1つずつ評価していくアプローチを取っていました。
これは「一番速そうなものをひとつ選ぶ」というシンプルなものですが、テーブル数が多くなったりJOINの条件が複雑になると、最適解にならない可能性があります。
一方、ハイパーグラフオプティマイザでは、クエリ全体を「ハイパーグラフ」として表現し、複数の結合条件をまとめて評価します。ハイパーグラフはグラフ理論で使われる言葉ですが、結合関係をエッジ、結合関係にあるテーブルをノードとしてハイパーグラフを構築します。その上でコストを評価し、効率的な実行計画を提供します。
t1,t2,t3と3つのテーブルが存在している場合は、それぞれの関係(サブプラン、下記1〜5)を洗い出し、ハイパーグラフを構築します。

t2
t3
t2 ⋈ t3
t1
t1 ⋈ (t2 ⋈ t3)

Hypergraph = 「クエリ全体をグラフ的に見て、より良い実行順序を探す」

ハイパーグラフオプティマイザのメリットは…？

複雑なJOINクエリに対する実行計画の最適化を行い、特にテーブルがたくさんある場合に性能が改善される可能性が高いと言われています。

試してみる

ハイパーグラフオプティマイザは一般公開されているMySQLでは有効化できず、有効にしようとするとエラーになります。現在、ハイパーグラフオプティマイザーを有効にするにはデバッグ版が必要になります。

MySQL> SET SESSION optimizer_switch='hypergraph_optimizer=on';
ERROR: 3999 (42000): The hypergraph optimizer does not yet support'use in non-debug builds'

従来のオプティマイザとの比較

今回は、MySQLのサンプルデータベースemployees データベースを利用して試してみると、従来のオプティマイザと比較すると34秒→23秒と約30%速くなりました。

実行環境

MySQL: 9.3 デバッグ版
OS: Oracle Linux8 (OCI VM.Standard.E5.Flex)
CPU: 1
Memory: 12GB

実行したSQL

SELECT e.emp_no, e.first_name, t.title, s.salary, d.dept_name 
FROM employees e 
JOIN titles t ON e.emp_no = t.emp_no 
JOIN salaries s ON e.emp_no = s.emp_no
JOIN dept_emp de ON e.emp_no = de.emp_no
JOIN departments d ON de.dept_no = d.dept_no
WHERE s.salary > 80000
AND t.title LIKE '%Engineer%'
AND d.dept_name = 'Development';

EXPLAIN ANALYZEの結果

従来のオプティマイザでは、ネストループとインデックス検索の実行に多くの処理コストがかかっているように見えます。一方、ハイパーグラフオプティマイザではハッシュ結合が多用されていて、処理コストが抑えられているようです。
また、OCIのコンソールでは、ハイパーグラフオプティマイザの方がCPU使用率も高くなっていました。

'hypergraph_optimizer=off'

 -> Nested loop inner join  (cost=220458 rows=159391) (actual time=6.89..34009 rows=111472 loops=1)
    -> Nested loop inner join  (cost=147079 rows=49112) (actual time=6.17..16200 rows=115230 loops=1)
        -> Nested loop inner join  (cost=97827 rows=49112) (actual time=5.46..11814 rows=115230 loops=1)
            -> Filter: (t.title like '%Engineer%')  (cost=45095 rows=49112) (actual time=4.9..2283 rows=227881 loops=1)
                -> Covering index scan on t using PRIMARY  (cost=45095 rows=442050) (actual time=4.89..1909 rows=443308 loops=1)
            -> Single-row covering index lookup on de using PRIMARY (emp_no = t.emp_no, dept_no = 'd005')  (cost=0.974 rows=1) (actual time=0.0413..0.0414 rows=0.506 loops=227881)
        -> Single-row index lookup on e using PRIMARY (emp_no = t.emp_no)  (cost=0.903 rows=1) (actual time=0.0374..0.0375 rows=1 loops=115230)
    -> Filter: (s.salary > 80000)  (cost=0.52 rows=3.25) (actual time=0.146..0.154 rows=0.967 loops=115230)
            -> Index lookup on s using PRIMARY (emp_no = t.emp_no)  (cost=0.52 rows=9.74) (actual time=0.109..0.15 rows=10.5 loops=115230)

'hypergraph_optimizer=on'

 -> Inner hash join (t.emp_no = s.emp_no)  (cost=1.56e+6..4.49e+6 rows=19056) (actual time=7356..23645 rows=111472 loops=1)
    -> Filter: (s.salary > 80000)  (cost=2.89..2.73e+6 rows=946101) (actual time=38.3..11635 rows=491466 loops=1)
        -> Table scan on s  (cost=0.904..2.57e+6 rows=2.84e+6) (actual time=38.3..10789 rows=2.84e+6 loops=1)
    -> Hash
        -> Inner hash join (e.emp_no = t.emp_no)  (cost=1.13e+6..1.55e+6 rows=6036) (actual time=3324..7203 rows=115230 loops=1)
            -> Table scan on e  (cost=1.22..365230 rows=299652) (actual time=7.48..1235 rows=300024 loops=1)
            -> Hash
                -> Inner hash join (t.emp_no = de.emp_no)  (cost=76294..1.12e+6 rows=6036) (actual time=453..3214 rows=115230 loops=1)
                    -> Filter: (t.title like '%Engineer%')  (cost=21..1.03e+6 rows=49112) (actual time=4.26..2148 rows=227881 loops=1)
                        -> Table scan on t  (cost=2.27..1e+6 rows=442050) (actual time=4.25..1852 rows=443308 loops=1)
                    -> Hash
                        -> Nested loop inner join  (cost=0.569..20968 rows=36826) (actual time=11.2..381 rows=85707 loops=1)
                            -> Single-row covering index lookup on d using dept_name (dept_name = 'Development')  (cost=2.34..2.34 rows=1) (actual time=0.0566..0.057 rows=1 loops=1)
                            -> Covering index lookup on de using dept_no (dept_no = d.dept_no)  (cost=0.569..20966 rows=36826) (actual time=11.2..365 rows=85707 loops=1)

比較結果

項目	従来のオプティマイザ	ハイパーグラフオプティマイザ
全体実行時間	~34,000ms	~23,645ms
salaries	115Kループ ✕ ~0.15ms = ~17秒	フルスキャン1回 → ~11秒
titles	~2秒強	~2秒強
dept_emp	~22万回 lookup	1回の index scan（~365ms）

まとめ

今回試してみた内容から、ハイパーグラフオプティマイザには以下の優位性があることが分かりました。

多重ループを排除し、ハッシュ結合で高速化
JOINが多くなるほど差が顕著に
従来のオプティマイザでは苦手だったパターンに効果的