クラスタリングファクタによってSQLのパフォーマンスが変わる話


昨日の実験では、両側にインデックスがある場合、マージ結合とネスト化ループ結合の速さがハッシュ結合と同等かそれ以上になってしまった。
少量のマスタと大量のトランザクションの結合は、ハッシュ結合が圧勝してしかるべきなので何だこりゃと思ったのだが、これはテストデータが都合よく整列しているせいだとわかったので、結合カラムの値を更新して測定し直してみた。

データを作り直す

昨日の時点では、トランザクションデータの作り方に問題があって、結合カラム(tid)が同じ値のレコードが一箇所に固まっていた。
こんな感じ:

bench=# select * from history limit 10;
 tid | bid |  aid   | delta |           mtime            |         filler         
-----+-----+--------+-------+----------------------------+------------------------
  20 |   2 | 119841 |   100 | 2009-01-07 15:11:23.537975 |                       
  20 |   2 | 119842 |   100 | 2009-01-07 15:11:23.537975 |                       
  20 |   2 | 119843 |   100 | 2009-01-07 15:11:23.537975 |                       
  20 |   2 | 119844 |   100 | 2009-01-07 15:11:23.537975 |                       
  20 |   2 | 119845 |   100 | 2009-01-07 15:11:23.537975 |                       
  20 |   2 | 119846 |   100 | 2009-01-07 15:11:23.537975 |                       
  20 |   2 | 119847 |   100 | 2009-01-07 15:11:23.537975 |                       
  20 |   2 | 119848 |   100 | 2009-01-07 15:11:23.537975 |                       
  20 |   2 | 119849 |   100 | 2009-01-07 15:11:23.537975 |                       
  20 |   2 | 119850 |   100 | 2009-01-07 15:11:23.537975 |                       

bench=# select * from history offset 1000000 limit 10;
 tid | bid |   aid   | delta |           mtime            |         filler         
-----+-----+---------+-------+----------------------------+------------------------
 120 |  12 | 1196881 |   100 | 2009-01-07 15:11:23.537975 |                       
 120 |  12 | 1196882 |   100 | 2009-01-07 15:11:23.537975 |                       
 120 |  12 | 1196883 |   100 | 2009-01-07 15:11:23.537975 |                       
 120 |  12 | 1196884 |   100 | 2009-01-07 15:11:23.537975 |                       
 120 |  12 | 1196885 |   100 | 2009-01-07 15:11:23.537975 |                       
 120 |  12 | 1196886 |   100 | 2009-01-07 15:11:23.537975 |                       
 120 |  12 | 1196887 |   100 | 2009-01-07 15:11:23.537975 |               
 120 |  12 | 1196888 |   100 | 2009-01-07 15:11:23.537975 |                       
 120 |  12 | 1196889 |   100 | 2009-01-07 15:11:23.537975 |                       
 120 |  12 | 1196890 |   100 | 2009-01-07 15:11:23.537975 |                       

実データであれば、tidの値はもっとバラバラになっていてもよい。
tidの値をランダムに変更することで、

update history
set tid = (random() * 1000)::int


データの配置を実データ風にした。

bench=# select * from history limit 10;
 tid | bid |   aid   | delta |           mtime            |         filler         
-----+-----+---------+-------+----------------------------+------------------------
 562 |  12 | 1196689 |   100 | 2009-01-07 15:11:23.537975 |                       
 517 |  12 | 1196690 |   100 | 2009-01-07 15:11:23.537975 |                       
 170 |  12 | 1196691 |   100 | 2009-01-07 15:11:23.537975 |                       
 655 |  12 | 1196692 |   100 | 2009-01-07 15:11:23.537975 |                       
  68 |  12 | 1196693 |   100 | 2009-01-07 15:11:23.537975 |                       
 514 |  12 | 1196694 |   100 | 2009-01-07 15:11:23.537975 |                       
 195 |  12 | 1196695 |   100 | 2009-01-07 15:11:23.537975 |                       
 542 |  12 | 1196696 |   100 | 2009-01-07 15:11:23.537975 |                       
 338 |  12 | 1196697 |   100 | 2009-01-07 15:11:23.537975 |                       
 152 |  12 | 1196698 |   100 | 2009-01-07 15:11:23.537975 |                       


ところで「インデックスの並び順と、データの並び順が似ている度合」のことをクラスタリングファクタというそうだ。
クラスタリングファクタが良好ならば(良好であることを low clustering factor というらしい)、1回のI/Oで欲しいデータをごっそり取ってキャッシュできるので、index range scan などによる大量ランダムアクセスのパフォーマンスが向上する。
ということは。
tidの値をでたらめに更新したことでクラスタリングファクタは悪化(=high clustering factor)したのだから、ネスト化ループ結合時に発生する大量のランダムアクセスが遅くなると予想できる。

結果

  • ハッシュ結合はデータの並び順の影響を受けない。速さは変わらなかった
  • マージ結合は、トランザクションのソートの作業量が増えて遅くなった(31秒->110秒)
  • ネスト化ループ結合は、index scanのコストが上がって遅くなった(30秒->120秒)

詳細

ハッシュ結合

31秒。データをバラバラにしても速さは変わらない。

                                                           QUERY PLAN                                                           
--------------------------------------------------------------------------------------------------------------------------------
 Hash Join  (cost=27.50..330093.53 rows=9910803 width=399) (actual time=1.643..25310.834 rows=9995026 loops=1)
   Hash Cond: (h.tid = t.tid)
   ->  Seq Scan on history h  (cost=0.00..193458.00 rows=10000000 width=47) (actual time=0.046..7304.755 rows=10000000 loops=1)
   ->  Hash  (cost=15.00..15.00 rows=1000 width=352) (actual time=1.585..1.585 rows=1000 loops=1)
         ->  Seq Scan on tellers t  (cost=0.00..15.00 rows=1000 width=352) (actual time=0.007..0.714 rows=1000 loops=1)
 Total runtime: 31381.892 ms
(6 rows)
マージ結合

トランザクション側のインデックスがなぜか使われていない。
実行計画はインデックスが片側だけにある時と同じだが、tid更新前よりも遅くなっている。

                                                                 QUERY PLAN                                                                  
---------------------------------------------------------------------------------------------------------------------------------------------
 Merge Join  (cost=2586659.11..2735760.61 rows=9910803 width=399) (actual time=65943.603..105096.873 rows=9995026 loops=1)
   Merge Cond: (t.tid = h.tid)
   ->  Index Scan using tellers_pkey on tellers t  (cost=0.00..43.25 rows=1000 width=352) (actual time=0.018..3.322 rows=1000 loops=1)
   ->  Materialize  (cost=2586606.83..2711606.83 rows=10000000 width=47) (actual time=65928.814..89628.564 rows=10000000 loops=1)
         ->  Sort  (cost=2586606.83..2611606.83 rows=10000000 width=47) (actual time=65928.809..75780.068 rows=10000000 loops=1)
               Sort Key: h.tid
               Sort Method:  external merge  Disk: 586264kB
               ->  Seq Scan on history h  (cost=0.00..193458.00 rows=10000000 width=47) (actual time=0.029..11862.312 rows=10000000 loops=1)
 Total runtime: 111347.370 ms
(9 rows)
ネスト化ループ結合

やはり遅くなった(30秒->110秒)。

                                                                   QUERY PLAN                                                                    
-------------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..34371115.97 rows=9910803 width=399) (actual time=4.096..115294.336 rows=9995026 loops=1)
   ->  Seq Scan on tellers t  (cost=0.00..15.00 rows=1000 width=352) (actual time=4.028..6.406 rows=1000 loops=1)
   ->  Index Scan using history_tid_idx on history h  (cost=0.00..34247.21 rows=9911 width=47) (actual time=0.056..100.362 rows=9995 loops=1000)
         Index Cond: (h.tid = t.tid)
 Total runtime: 121517.932 ms
(5 rows)

まとめ

実行計画のパフォーマンスは

  • データの件数
  • データの偏り具合(カーディナリティ)
  • データの配置場所の固まり具合(クラスタリングファクタ)

といった、データの状態に影響を受ける。
対象のデータがどういう状態にあるかがわからないと、「こういうインデックスがあって、この結合方式だから、実行すると速い(or遅い)」という話は、本当はできない。