mysql - 階層データ全体での MySQL クエリの最適化

Question

頂点数が 100k 以下、エッジ数が 1k 以下のかなり安定した有向グラフがあります。(x, y)頂点が(カーディナリティ ~100 x ~1000 の)整数のペアで識別でき、すべてのエッジが で厳密に増加している限り、これは 2 次元xです。

(key, val)さらに、各頂点に関連付けられた~1k ペアのディクショナリがあります。

私は現在、3つの（InnoDB）テーブルにまたがるMySQLデータベースにグラフを保存しています：頂点のテーブル（これは私の質問に関連しているとは思わないので、それと参照する外部キー制約の両方を含めることを省略しました以下の私の抜粋にあります）; 辞書を保持するテーブル。ビル・カーウィンが雄弁に説明したように、接続された頂点の「クロージャテーブル」。

頂点辞書のテーブルは次のように定義されます。

CREATE TABLE `VertexDictionary` (
  `x`   smallint(6) unsigned NOT NULL,
  `y`   smallint(6) unsigned NOT NULL,
  `key` varchar(50) NOT NULL DEFAULT '',
  `val` smallint(1) DEFAULT NULL,
  PRIMARY KEY (`x`, `y`  , `key`),
  KEY  `dict` (`x`, `key`, `val`)
);

接続された頂点の閉包表は次のようになります。

CREATE TABLE `ConnectedVertices` (
  `tail_x` smallint(6) unsigned NOT NULL,
  `tail_y` smallint(6) unsigned NOT NULL,
  `head_x` smallint(6) unsigned NOT NULL,
  `head_y` smallint(6) unsigned NOT NULL,
  PRIMARY KEY   (`tail_x`, `tail_y`, `head_x`),
  KEY `reverse` (`head_x`, `head_y`, `tail_x`),
  KEY `fx` (`tail_x`, `head_x`),
  KEY `rx` (`head_x`, `tail_x`)
);

ペアの辞書もあり、(x, key)そのようなペアごとに、 that で識別されるすべての頂点xが辞書内に that の値を持っていますkey。このディクショナリは 4 番目のテーブルに格納されます。

CREATE TABLE `SpecialKeys` (
  `x`   smallint(6) unsigned NOT NULL,
  `key` varchar(50) NOT NULL DEFAULT '',
  PRIMARY KEY (`x`),
  KEY `xkey`  (`x`, `key`)
);

特定の を持つすべての頂点の辞書で使用されるキーのセットを、左に接続されたx=Xany の関連する値とともに抽出したいことがよくあります。SpecialKeys

SELECT DISTINCT
  `v`.`key`,
  `u`.`val`
FROM
       `ConnectedVertices` AS `c`
  JOIN `VertexDictionary`  AS `u` ON (`u`.`x`, `u`.`y`  ) = (`c`.`tail_x`, `c`.`tail_y`)
  JOIN `VertexDictionary`  AS `v` ON (`v`.`x`, `v`.`y`  ) = (`c`.`head_x`, `c`.`head_y`)
  JOIN `SpecialKeys`       AS `k` ON (`k`.`x`, `k`.`key`) = (`u`.`x`, `u`.`key`)
WHERE
  `v`.`x` = X
;

EXPLAIN出力は次のとおりです。

id select_type テーブル タイプ possible_keys キー key_len ref 行 エクストラ
 1 SIMPLE k index PRIMARY,xkey xkey 154 NULL 40 インデックスを使用。一時的な使用
 1 SIMPLE c ref PRIMARY,reverse,fx,rx PRIMARY 2 db.kx 1 where の使用
 1 SIMPLE v ref PRIMARY,dict PRIMARY 4 const,db.c.head_y 136 インデックスの使用
 1 SIMPLE u eq_ref PRIMARY,dict PRIMARY 156 db.c.tail_x,db.c.tail_y,db.k.key 1 where の使用

ただし、このクエリは完了するまでに 10 秒ほどかかります。問題を改善しようとしてレンガの壁に頭をぶつけていましたが、役に立ちませんでした。

クエリを改善できますか、または別のデータ構造を検討する必要がありますか? あなたの考えに非常に感謝します！

---

アップデート

テーブルを再構築したところ、出力がわずかに異なることがわかりましたEXPLAIN(上記のように、フェッチされた行の数がv1 から 136 に増加しました!)。クエリの実行にはまだ 10 秒ほどかかります。

ここで何が起こっているのか本当にわかりません。(x, y, SpecialValue)すべてのタプルとすべてのタプルを取得するためのクエリ(x, y, key)はどちらも非常に高速ですが (それぞれ約 30 ミリ秒と約 150 ミリ秒)、基本的に 2 つの結合には合計時間の 50 倍の時間がかかります... その結合を実行するのにかかる時間を改善するにはどうすればよいですか?

以下の出力SHOW VARIABLES LIKE '%innodb%';：

変数名 値
-------------------------------------------------- ----------
have_innodb はい
ignore_builtin_innodb オン
innodb_adaptive_flushing ON
innodb_adaptive_hash_index オン
innodb_additional_mem_pool_size 2097152
innodb_autoextend_increment 8
innodb_autoinc_lock_mode 1
innodb_buffer_pool_size 1179648000
innodb_change_buffering 挿入
innodb_checksums オン
innodb_commit_concurrency 0
innodb_concurrency_tickets 500
innodb_data_file_path ibdata1:10M:autoextend
innodb_data_home_dir /rdsdbdata/db/innodb
innodb_doublewrite オン
innodb_fast_shutdown 1
innodb_file_format アンテロープ
innodb_file_format_check バラクーダ
innodb_file_per_table オン
innodb_flush_log_at_trx_commit 1
innodb_flush_method O_DIRECT
innodb_force_recovery 0
innodb_io_capacity 200
innodb_lock_wait_timeout 50
innodb_locks_unsafe_for_binlog オフ
innodb_log_buffer_size 8388608
innodb_log_file_size 134217728
innodb_log_files_in_group 2
innodb_log_group_home_dir /rdsdbdata/log/innodb
innodb_max_dirty_pages_pct 75
innodb_max_purge_lag 0
innodb_mirrored_log_groups 1
innodb_old_blocks_pct 37
innodb_old_blocks_time 0
innodb_open_files 300
innodb_read_ahead_threshold 56
innodb_read_io_threads 4
innodb_replication_delay 0
innodb_rollback_on_timeout オフ
innodb_spin_wait_delay 6
innodb_stats_method nulls_equal
innodb_stats_on_metadata オン
innodb_stats_sample_pages 8
innodb_strict_mode オフ
innodb_support_xa オン
innodb_sync_spin_loops 30
innodb_table_locks オン
innodb_thread_concurrency 0
innodb_thread_sleep_delay 10000
innodb_use_sys_malloc オン
innodb_バージョン 1.0.16
innodb_write_io_threads 4

Answer 1

テストに時間をかけずに、不完全な例を提供しましたか? 結合されたテーブルの並べ替えを必ず試してください。説明出力はいくつかの情報を提供します。key_len による順序付けがヒューリスティックに最速であるとしましょう。オプティマイザーがそれを把握できない場合に備えて、フィルタリングする最初のテーブルを最後にリストする必要があると思います。

では、'c, v, k, u' の順番がベストだとしましょう。

SELECT DISTINCT
  `v`.`key`,
  `u`.`val`
FROM
  `VertexDictionary`  AS `u`
  JOIN `SpecialKeys`       AS `k` ON (`k`.`x`, `k`.`key`) = (`u`.`x`, `u`.`key`)
  JOIN `VertexDictionary`  AS `v`
  JOIN `ConnectedVertices` AS `c` ON (`u`.`x`, `u`.`y`  ) = (`c`.`tail_x`, `c`.`tail_y`)
           AND (`v`.`x`, `v`.`y`  ) = (`c`.`head_x`, `c`.`head_y`)
WHERE
  `v`.`x` = X
;

「行」は「c/u、k、v」の順序を示唆しますが、それはデータに依存します:

SELECT DISTINCT
  `v`.`key`,
  `u`.`val`
FROM
  `VertexDictionary`  AS `u`
  JOIN `VertexDictionary`  AS `v`
  JOIN `SpecialKeys`       AS `k` ON (`k`.`x`, `k`.`key`) = (`u`.`x`, `u`.`key`)
  JOIN `ConnectedVertices` AS `c` ON (`u`.`x`, `u`.`y`  ) = (`c`.`tail_x`, `c`.`tail_y`)
                                 AND (`v`.`x`, `v`.`y`  ) = (`c`.`head_x`, `c`.`head_y`)
 WHERE
  `v`.`x` = X
;

お役に立てれば。

更新(varchar 結合を回避):

SELECT DISTINCT
  `v`.`key`,
  `u`.`val`
FROM
       `ConnectedVertices` AS `c`
  JOIN `VertexDictionary`  AS `u` ON (`u`.`x`, `u`.`y`  ) = (`c`.`tail_x`, `c`.`tail_y`)
  JOIN `VertexDictionary`  AS `v` ON (`v`.`x`, `v`.`y`  ) = (`c`.`head_x`, `c`.`head_y`)
WHERE
  (`u`.`x`, `u`.`key`) IN (SELECT `k`.`x`, `k`.`key` FROM `SpecialKeys` AS `k`)
AND
  `v`.`x` = X
;

Answer 2

DISTINCT多くの場合、悪い友達です。に置き換えてみてくださいGROUP BY。このような ：

SELECT sub.key, sub.val
FROM (
    SELECT 
      v.key,
      u.val
    FROM
      ConnectedVertices AS c
      JOIN VertexDictionary  AS u ON (u.x, u.y  ) = (c.tail_x, c.tail_y)
      JOIN VertexDictionary  AS v ON (v.x, v.y  ) = (c.head_x, c.head_y)
      JOIN SpecialKeys       AS k ON (k.x, k.key) = (u.x, u.key)
    WHERE (v.x = @X)
) AS sub
GROUP BY sub.key, sub.val

アップデート：

次に、インデックスを強制的に使用する次のクエリを試してください。

SELECT DISTINCT
  v.key,
  u.val
FROM
  ConnectedVertices AS c USE INDEX (fx,rx)
  JOIN VertexDictionary  AS u USE INDEX (primary) ON (u.x, u.y  ) = (c.tail_x, c.tail_y) 
  JOIN VertexDictionary  AS v USE INDEX (primary) ON (v.x, v.y  ) = (c.head_x, c.head_y)
  JOIN SpecialKeys       AS k USE INDEX (primary) ON (k.x, k.key) = (u.x, u.key)
WHERE (v.x = @X)

それでもうまくいかない場合は、これを試してください：

SELECT DISTINCT
  v.key,
  u.val
FROM
       ConnectedVertices AS c
  JOIN VertexDictionary  AS u ON (u.x=c.tail_x) AND (u.y=c.tail_y)
  JOIN VertexDictionary  AS v ON (v.x=@X) AND (v.y=c.head_y)
  JOIN SpecialKeys       AS k ON (k.x=u.x) AND (k.key=u.key)
WHERE
  v.x = @X

Answer 3

あなたの問題は構文のすべてだと思います

( k. x, k. key) = ( u. x, u. key)

のように書き直すことはできますか？

kx = yx および k.key = u.key

句の左側に計算がある場合、dbms は最適化できません。比較を直接比較として設定すると、パフォーマンスが向上する場合があります。

例えば

年 (私の日付) = '2012'

より遅い

'2012' = 年 (私の日付)

mysql が比較を列の比較として扱うのか、それとも計算として扱うのかはわかりません。

列の値を比較するようにクエリを変更してみてください。

---

2 番目の最適化

また、4 つのテーブルをクロス結合しています。乗算は加法的ではなく、指数関数的です。これが意図したものであると確信していますか? 最小の結果セットから始めて、その結果セットのみを次のセットに結合することをお勧めします。

select a.c1
from (
select t1.c1
from t1
join t2 on t1.c1 = t2.c1
) a
join t3 on t3.c1 = a.c1

等...

---

3 番目の最適化

オプション 2 が役立つ場合は、テーブルから直接ではなく、インデックス付きビューを作成してそれらから作業することをお勧めします。

---

4 回目の最適化

mysql を使用しないでください。パフォーマンスと微調整を常に監視している dbas のチームがいない限り、mysql で悪い時期に遭遇するでしょう。mysql は単純なことでは問題なく高速ですが、適度に複雑なことを行うと、非常にうまく機能しなくなります。4 年前、私は mysql から sql server express に移行しましたが、同じテーブル、インデックス、およびクエリで 10 分のクエリに 2 秒未満かかりました...

オープンソースが必要な場合、postgres は mysql よりもはるかにスマートです

---

v.key、u.val フィールドでインデックス付けされた最初の 3 つのテーブルを組み込んだビューを作成します。次に、4 番目のテーブルとビューからクエリを実行します。実行する前に、インデックスがビューに構築されていることを確認してください。

Answer 4

クエリを段階的に再構築してみてください。少なくとも、ボトルネックがどこにあるかを特定するためのポイントをいくつか教えてください。次のクエリのいくつかの組み合わせは、スキーマまたはデータ セットを変更せずに可能であれば、妥当なパフォーマンスを提供するはずです。

適切な末尾の頂点 (つまり、SpecialKey を持つもの) のリストを取得するための次のクエリの行数と実行時間は?

SELECT -- DISTINCT
    vd.x as tail_x, vd.y as tail_y, vd.val
FROM
    VertexDictionary vd
WHERE
    EXISTS (
        SELECT
            1
        FROM
            SpecialKeys sk
        WHERE
            vd.x = sk.x
        AND
            vd.key = sk.key
    )

また

SELECT -- DISTINCT
    vd.x as tail_x, vd.y as tail_y, vd.val
FROM
    VertexDictionary vd
JOIN
    SpecialKeys sk
ON
    vd.x = sk.x
AND
    vd.key = sk.key

また

SELECT -- DISTINCT
    vd.x as tail_x, vd.y as tail_y, vd.val
FROM
    VertexDictionary vd
WHERE
(vd.x, vd.key) IN (SELECT x, key FROM SpecialKeys)
-- also could try vd.key IN (SELECT sk.key FROM SpecialKeys sk WHERE sk.x = vd.x)

これらのいずれかが小さな結果セットを返すか、少なくとも迅速に結果を生成することを願っています。カーディナリティが低く、結果が大きい場合は、個別に適用されます。

前の 2 つのクエリから最適なものを選択し、次のステップに追加します。これらの適切な「テール」を「適切なヘッド」に結合します。

SELECT -- DISTINCT
    cv.head_y as y,
    tv.val
FROM
(
    -- ADD SUB QUERY HERE also try nesting the subquery like: (select tail_x, tail_y, val from ([SUBQUERY]) as sq)

) as tv -- tail verticies
JOIN
    ConnectedVerticies cv
ON
    cv.tail_x = tv.tail_x
AND
    cv.tail_y = tv.tail_y
WHERE
    cv.head_x = X -- lets reduce the result set here.

繰り返しますが、これらのいずれかが小さな結果セットを返すか、少なくとも迅速に結果を生成することを望んでいます。カーディナリティが低く、結果が大きい場合は、個別に適用されます。

この時点で失敗している場合は、最後のフェーズを適用するのが速くなるという期待はあまりなく、別のアプローチを試すのが最善です.

head x は前のクエリでわかっているので、head_y と X を結合して v.key を取得するだけです。

SELECT DISTINCT
    inner_query.val,
    head.key
FROM
(
 -- previous nested subquery behemoth here, again, try a few things that might work.

) as inner_query
JOIN
    VertexDictionary as head
ON
    head.x = X
AND
    head.y = inner_query.y

別のアプローチは、head.key、tail_x、および tail_y のリストを取得することです。

SELECT -- DISTINCT
    cv.tail_x as x,
    cv.tail_y as y,
    vd.key
FROM
    VertexDictionary vd
JOIN
    ConnectedVerticies cv
ON
    cv.head_x = vd.x
AND
    cv.head_y = vd.y
WHERE
    vd.head_x = X

これを実行するのにどれくらいの時間がかかりますか? いくつの結果が得られましたか (区別あり、なし)?

高速かつ/または小さい場合は、それをサブクエリとして使用し、それが小さい場合は SpecialKeys および VertexDictionary の別のサブクエリの可能性に参加してみてください (つまり、うまく機能する場合は最初の 3 つのクエリの 1 つ)。

Answer 5

i don't think that forcing uses of specifique indexes is a good think. the Mysql optimiser has often good estimations.

do you have an index on v.x ?

Answer 6

他の人は同意しないかもしれませんが、私はクエリに STRAIGHT_JOIN を定期的に提供してきました...データと関係を知ったら。WHERE 句が "V" テーブル エイリアスとそれが "x" 値に反しているため、インデックスに問題はありません。それを前の位置に移動し、そこから参加します。

SELECT STRAIGHT_JOIN DISTINCT
      v.`key`,
      u.`val`
   FROM
      VertexDictionary AS v 

         JOIN ConnectedVertices AS c
            ON v.x = c.head_x
            AND v.y = c.head_y

            JOIN VertexDictionary AS u 
               ON c.tail_x = u.x 
               AND c.tail_y = u.y

               JOIN SpecialKeys AS k
                  ON u.x = k.x
                  AND u.key = k.key
   WHERE
      v.x = {some value}      

この再調整がどのように機能するか知りたい