Help us understand the problem. What is going on with this article?

MariaDBのブロックハッシュ結合

More than 1 year has passed since last update.

1.MySQLのJOINアルゴリズム

MySQLは従来からJOINする際に使用するアルゴリズムはネステッド・ループのみと聞いてきました。そこからフォークしたMariaDBも同様だと、今まで認識していました。
ところが最近下記の記事を知りました。

https://mariadb.com/kb/en/library/block-based-join-algorithms/
(Google翻訳)
https://translate.google.com/translate?hl=ja&sl=en&tl=ja&u=https%3A%2F%2Fmariadb.com%2Fkb%2Fen%2Flibrary%2Fblock-based-join-algorithms%2F
ここにはMariaDB 5.3で「ブロックハッシュ結合」が可能になった、とあります。

そこで少々動きについて調べてみました。

2.環境

試したのは

・Windows 10 Pro
・MariaDB 10.2.15

my.ini 以下のパラメータの修正、追加

・join_cache_level = 8
・optimizer_switch='optimize_join_buffer_size=on,mrr=on,mrr_cost_based=on'
・join_buffer_size 128K → 4M
・join_buffer_space_limit = 64M

・テスト用のテーブル

create table t ( id int, col1 varchar(255), col2 varchar(255) )

主キー、インデックスはなし

・データ

idに1から1000の連番、col1, col2は'a'と'b'で埋める

・SQL

select t1.*, t2.*
from t t1 join t t2
on t1.id = t2.id

あまり細かいことは考慮していません

3.実行計画の確認

+------+-------------+-------+----------+---------------+-----------+---------+------------+------+--------------------------------------------------+
| id   | select_type | table | type     | possible_keys | key       | key_len | ref        | rows | Extra                                            |
+------+-------------+-------+----------+---------------+-----------+---------+------------+------+--------------------------------------------------+
|    1 | SIMPLE      | t1    | ALL      | NULL          | NULL      | NULL    | NULL       | 1000 | Using where                                      |
|    1 | SIMPLE      | t2    | hash_ALL | NULL          | #hash#$hj | 5       | test.t1.id | 1000 | Using where; Using join buffer (flat, BNLH join) |
+------+-------------+-------+----------+---------------+-----------+---------+------------+------+--------------------------------------------------+
2 rows in set (0.00 sec)

実行計画の「key」に「#hash#$hj」が出現。
「extra」に「Using join buffer (flat, BNLH join)」が。
BNLHは Block Nested Loop Hash とのこと。

4.感想

とりあえず、MariaDBではハッシュ結合が出来るようです。
ただ、デフォルトの設定では有効になっていません。
この理由はよくわかりません。
確かに多数のセッションからアクセスがかかる場合、ハッシュ結合よりもインデックスを利用したアクセスパスのほうが効率的で使用メモリが少ないことは確かです。
動作としてjoin_buffer_sizeのメモリを常に確保する仕様だとワーカースレッド数が増えると無視できなくなります。
PostgreSQLなどだとけっこうハッシュ結合を実行計画として採用する傾向があります。
なお、PostgreSQLやORACLEなどだとSemi JOIN、Anti Joinでもハッシュ結合を採用しますが今回のテストでは確認できませんでした。
現在のMaiaDB開発陣のハッシュ結合についての評価の反映かもしれません。

なお、今回はあくまで動作に関することですので、実行パフォーマンスについての評価計測などは行っていません。
ハッシュ結合が常にパフォーマンス的に優れているわけではありません。
時間に余裕ができたら、いくつかのパターンで比較したいとは思っています。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした