Big-O for SQLの選択は何ですか？

Question

n行のテーブルに対して、Big-O for SQLを選択すると、mの結果が返されますか？

Update、またはdelete、またはCreateの操作でBig-Oとは何ですか？

私は一般的にmysqlとsqliteについて話しています。

Answer 1

選択したアルゴリズムを制御しないので、直接知る方法はありません。しかし、インデックスがなければ、SELECTはO（n）でなければなりません（テーブルスキャンはすべてのレコードを検査しなければなりません。つまり、テーブルのサイズに比例します）。

インデックスを使用すると、SELECTはおそらくO（log（n））です（ただし、インデックスは実際の表に当てはまる場合は索引付けに使用するアルゴリズムとデータ自体のプロパティによって異なります）。テーブルやクエリの結果を確認するには、実際のデータをプロファイリングして確認する必要があります。

インデックスを持たないINSERTは非常に速く（O（1に近い））、UPDATEはレコードを最初に見つけ出す必要があり、そこで取得するSELECTよりも（わずかに）遅くなるはずです。

インデックスを持つINSERTは、インデックスツリーを再調整する必要がある場合はおそらくO（log（n^2））、それ以外の場合はO（log（n））に近いと考えられます。 SELECTコストの上で、索引付き行に影響する場合、UPDATEで同じ減速が発生します。

ミックスでJOINを話すと、すべてのベットはオフになります。データベースクエリの見積もりツールをプロファイルして使用する必要があります。また、このクエリがパフォーマンスに重大な影響を及ぼす場合は、クエリのオプティマイザで使用されるアルゴリズムがデータの負荷が変化するにつれて変更されるため、時折というプロファイルを使用する必要があります。

覚えておくべきもう1つのこと... big-Oは、各取引の固定費については教えていません。小さなテーブルの場合、実際の作業コストよりも高い可能性があります。例として、単一行のクロスネットワーククエリのセットアップ、ティアダウン、および通信コストは、小さなテーブルのインデックス付きレコードのルックアップ以上になります。

このため、関連するクエリのグループを1つのバッチにバンドルできると、データベースの最適化よりもパフォーマンスに大きな影響を与える可能性があることがわかりました。

Answer 2

実際の答えは、ケースバイケースでのみ決定できると思います（データベースエンジン、テーブルデザイン、インデックスなど）。

ただし、MS SQL Serverユーザーの場合は、Query Analyzer（2000）またはManagement Studio（2005+）の見積もり実行計画に慣れることができます。これにより、分析に使用できる多くの情報が得られます。

Answer 3

すべては、あなたのSQLをどのように書くか、実行している操作のためにデータベースがどれだけうまく設計されているかによって異なります。 EXPLAIN PLAN機能を使用して、DBがどのように実行されるかを確認してください。 。あなたはbig-Oを計算することができます