2

count、sum、avg、または mysql、sql server、oracle などの組み込みの「数学」関数などの関数の時間計算量はどれくらいですか?

sum(myColumn) の呼び出しは線形であると考える人もいるでしょう。

しかし count(1) はそうではありません。リアルタイムの複雑さとはどのようなものでしょうか?

完璧な世界では、sum、avg、count を O(1) にしたいと思います。しかし、私たちはそれらのいずれにも住んでいませんよね？

4

4 に答える 4

5

count、sum、avg、またはその他の組み込みの「数学」関数（mysql、sql server、oracleなどの関数）の時間計算量はどれくらいですか？

  • MySQLあり、なしMyISAM（定数）COUNT(*)GROUP BYO(1)

    テーブルのメタデータに保存されます。

  • すべてのシステムで、MAXおよびMINインデックス付きの式では、 GROUP BYare O(log(n))（対数）がありません。

    それらは単一のインデックスシークでフェッチされます。

  • なしで使用した場合、または使用した場合、集計関数はO(n)（線形）ですGROUP BYGROUP BYHASH

  • 集計関数はO(n log(n))、GROUP BYを使用する場合SORTです。

All values should be fetched, calculated and stored in the state variables (which may be stored in a hash table).

In addition, when using SORT, they should also be sorted.

于 2009-10-09T11:14:57.983 に答える
3

SQL では、集計の数学関数の複雑さはまったく関係ありません。本当に重要なのは、データ アクセスの複雑さだけです。どのアクセス パスが選択されているか (テーブル スキャン、インデックス レンジ スキャン、インデックス シークなど) と、読み取られるページ数です。各集約の内部にはわずかな違いがあるかもしれませんが、それらはすべてほぼ同じように機能し (実行状態を維持し、入力値ごとに実行中の集約を計算します)、入力を 2 回見る集約はまったくないため、すべてO (n) 内部実装として。ここで、'n' は集計に供給されるレコードの数です (必ずしもテーブル内のレコードの数ではありません!)。

一部の集計には内部ショートカットがあります。COUNT(*)は、可能であれば、一部のシステムのメタデータからカウントを返す場合があります。

于 2009-10-07T21:51:13.333 に答える
2

注: これは、SQL クエリ プランナーがどのように機能するかについての私の理解に基づく推測であり、完全に正確ではない可能性があります。

すべての集計関数、または少なくとも上記で名前を付けた「数学」関数は O(n) である必要があると思います。クエリは、おおよそ次のように実行されます。

  1. 結合述語とフィルター述語 (つまり、「WHERE 句」) に一致する行をフェッチします。
  2. GROUP BY 句に従って行グループを作成します。GROUP BY のないクエリに対して単一の行グループが作成されます。
  3. 行グループごとに、集計関数をグループ内の行に適用します。SUM、AVG、MIN、MAX、および CONCAT などの非数値関数には、単純な O(n) アルゴリズムがあり、それらが使用されていると思われます。ステップ 2 で作成した行グループごとに、出力セットに 1 つの行を作成します。
  4. HAVING 述語が存在する場合、この述語を使用して出力行をフィルタリングします

ただし、集計関数が O(n) であっても、操作はそうではない可能性があることに注意してください。テーブルをそれ自体にデカルト結合するクエリを作成する場合、最初の行セットを作成するためだけに O(n*n) の最小値を調べることになります (ステップ #1)。行グループを作成するための並べ替え (ステップ 2) は O(n lg n) になる可能性があり、並べ替え操作にはディスク ストレージが必要になる場合があります (インメモリ操作のみとは対照的に)。多くの行を操作します。

于 2009-10-07T21:08:40.000 に答える
0

ビッグ データ ウェアハウス スタイルのクエリの場合、主要なデータベースはタスクを並列化できるため、複数の CPU で処理できます。したがって、並列スレッドを調整するコストが複数の CPU を使用する利点とトレードオフするため、線形ではないしきい値ポイントが存在します。

于 2009-10-09T08:38:25.340 に答える