NOT IN（）を使用したクエリの効率？

Question

私は自分のサーバー上で実行されるクエリを持っています。

DELETE FROM pairing WHERE id NOT IN (SELECT f.id FROM info f) 

そのペアリングのidがinfoでないときそれはpairingからすべてのエントリを2つの異なるテーブル、pairingを取り、infoとDELETEに述べています。

これは実行に時間がかかりすぎるサーバーで問題が発生しました。これは効率（またはSELECTステートメントの制約がない）と関係していると思います。

しかし、私はMySQL slow_logを見ましたが、比較されるエントリの数は実際にはLOWERである必要があります。私の理解から、これはO（mn）時間であるべきです。ここで、mはpairingのエントリの数であり、nはinfoのエントリの数です。 pairingのエントリ数は26,868、infoのエントリ数は34,976です。

これは、939,735,168回の比較を追加します。しかし、slow_logにはわずか543,916,401しかないと言われています。

私は、この特定のクエリの効率がどのように作用するかを私に説明してもらえないかと考えていました。私はそれがこの場合の祝福であるべきだと思うより速く実行しているという事実を理解していますが、私はそれをさらに改善できるように最適化がどこから来るのかを理解する必要があります。

Answer 1

私は低速のクエリログをあまり使用していませんが、その違いが単なる単純化されている可能性はありません...その言葉を考えることはできません。基本的に939,735,168は、最初に必要なものを除くすべての単一の行を照会が文字通りチェックする理論的な最悪のシナリオです。現実的には、ほぼ均等な分布（インデックスの使用なし）の場合、pairingの行のチェックは平均でinfoの行の半分と比較します。

実際の世界のパフォーマンスは「平均的な比較」から予想されるものよりもわずか15％（悪化）です。

編集：実際には、の行がinfoにない場合は、比較の数がずれてしまうため、「予想よりも悪い」と予想されます。それでも素晴らしいではありません

---

...。あなたが両方のテーブルでインデックスを持つidを持っているなら、このようなものはもっと速く動作するはずです。

DELETE pairing 
FROM pairing LEFT JOIN info ON pairing.id = info.id 
WHERE info.id IS NULL 
; 

これはO（NlogM）のようなものを必要な比較を行うことidにインデックスを活用すべきです。