3

質問

私はコンプ科学の専門家ではないので、用語を混乱させてしまった場合はご容赦ください。呼び出しの計算量はどのくらいですか

 SELECT DISTINCT(column) FROM table

また

SELECT * FROM table GROUP BY column

インデックスが作成された列で? 行数または列内の個別の値の数に比例しますか。O(1)*NUM_DISINCT_COLS私はそれがvsになると信じていますO(NUM_OF_ROWS)

バックグラウンド

たとえば、1,000 万行あるが、その列に 10 個の個別の値/グループしかない場合、各グループの最後の項目を単純に数えることができるため、時間の複雑さは行の数ではなく個別のグループの数に関連付けられます。したがって、100万行の場合と100行の場合の計算には同じ時間がかかります。複雑さは次のようになると思います

O(1)*Number_Of_DISTINCT_ELEMENTS

しかし、MySQL の場合、10 個の個別のグループがある場合、MySQL は依然としてすべての行をシークし、基本的に各グループの実行中のいくつかを計算しますか、または同じ値の行のグループを計算できるように設定されていますか?個別の列値ごとに O(1) 時間で? そうでない場合、それは複雑さが

O(NUM_ROWS)

なぜ私は気にするのですか？

私のサイトには、未読の合計、メッセージの合計など、メッセージのカテゴリの統計を一覧表示するページがあります。この情報は and を使用して計算できますGROUP BYがSUM()、メッセージの数が増えると時間がかかるという印象を受けました。各カテゴリの統計表があります。新しいメッセージが送信または作成されると、total_messages フィールドをインクリメントします。州のページを表示したいときは、単一​​の行を選択するだけです

SELECT total_unread_messages FROM stats WHERE category_id = x

GROUP BYこれらの統計を計算する代わりに、および/またはを使用して、すべてのメッセージにわたって生きていますDISINCT。

私の場合、どちらの方法でもパフォーマンスへの影響は大きくないため、これは「時期尚早の最適化」のケースのように思えるかもしれませんが、他のオプションに関してスケーラブルである、またはスケーラブルでないことをいつ実行しているかを知ることは良いことです.構築にそれほど時間はかかりません。

4

1 に答える 1

3

あなたがしている場合：

select distinct column
from table

にインデックスがありcolumn、MySQL は「ルーズ インデックス スキャン」(ここで説明) を使用してこのクエリを処理できます。

これにより、エンジンはインデックスから 1 つのキーを読み取り、中間キー (すべて同一) を読み取らずに次のキーに「ジャンプ」できるようになります。これは、操作でインデックス全体を読み取る必要がないことを示唆しているため、一般にO(n)(where n= テーブル内の行数) よりも少なくなります。

次の値を見つけるのに 1 回の操作しか必要ないとは思えません。全体的な複雑さが のようなものであったとしても、私は驚かないでしょう。O(m * log(n))ここでm= 異なる値の数。

于 2013-08-22T18:31:44.223 に答える