行を含むテーブルで、結果nを返したいSQL 選択の Big-O とは何ですか?m
Update、またはdelete、またはCreate操作の Big-O とは何ですか?
私は一般的にmysqlとsqliteについて話しています。
17660 次
3 に答える
54
選択したアルゴリズムを制御できないため、直接知る方法はありません。ただし、インデックスがない場合、SELECT は O(n) にする必要があります (テーブル スキャンでは、すべてのレコードを検査する必要があります。これは、テーブルのサイズに合わせてスケーリングすることを意味します)。
インデックスを使用すると、SELECT はおそらく O(log(n)) になります (ただし、実際のテーブルに当てはまる場合は、インデックス作成に使用されるアルゴリズムとデータ自体のプロパティに依存します)。テーブルまたはクエリの結果を判断するには、実際のデータを確実にプロファイリングする必要があります。
インデックスなしの INSERT は非常に高速 (O(1) に近い) である必要がありますが、UPDATE は最初にレコードを見つける必要があるため、そこに到達する SELECT よりも (わずかに) 遅くなります。
インデックス ツリーを再調整する必要がある場合、インデックスを使用した INSERT はおそらく O(log(n^2)) の球場にあり、それ以外の場合は O(log(n)) に近くなります。SELECT コストに加えて、UPDATE がインデックス付きの行に影響を与える場合、UPDATE でも同じ速度低下が発生します。
JOIN について話していると、すべての賭けが外れます。それを読み取るには、プロファイルを作成し、データベース クエリ推定ツールを使用する必要があります。また、このクエリがパフォーマンス クリティカルである場合は、クエリ オプティマイザが使用するアルゴリズムがデータ ロードの変化に応じて変化するため、時々プロファイルを変更する必要があることに注意してください。
心に留めておくべきもう 1 つのことは... big-O は、各トランザクションの固定費について教えてくれません。小さいテーブルの場合、これらはおそらく実際の作業コストよりも高くなります。例として、単一の行に対するクロス ネットワーク クエリのセットアップ、破棄、および通信コストは、小さなテーブルのインデックス付きレコードのルックアップよりも確実に高くなります。
このため、関連するクエリのグループを 1 つのバッチにまとめることができると、データベース自体に対して行った最適化よりもパフォーマンスに大きな影響を与える可能性があることがわかりました。
于 2009-08-28T15:03:58.420 に答える
0
すべては、SQL をどのように (適切に) 記述するか、および実行する操作に対してデータベースがどの程度適切に設計されているかに依存します。Explain Plan 関数を使用して、データベースがどのように実行されるかを確認してください。。Big-O を計算できます
于 2009-08-28T15:09:20.737 に答える