9

SQL テーブルの行数を数える最良の方法は count(*) (または同等に count(PrimaryKey)) であることを理解しています。

  1. これは O(1) ですか?
  2. そうでない場合、なぜですか？

カウンターを実装して、この特定のクエリに対してそれを返さないのはなぜですか? このクエリが一般的な使用例ではないためですか?

SQL エンジンによって答えが異なる場合は、その違いを聞きたいと思いますが、いずれにせよ、本番 SQL​​ エンジンでの実際の実装に興味があります。

4

11 に答える 11

9

一部のRDBMでは、これはO（1）（特にMySQL）であり、一般的に眉をひそめ、「醜いパフォーマンスハック」と見なされるAFAIKを置きます。その理由は、トランザクション（すべての実際のRDBMが持つ必要がある）がある場合、テーブル内の行の総数は、現在のトランザクションから確認できる総数と等しい場合と等しくない場合があるためです。これが、サーバーがトランザクションに実際に表示される行をチェックする必要がある理由であり、O（1）よりもO（n）が多くなります。

行数を取得するプロセスを最適化し、おおよその結果に満足する場合、ほとんどのRDBMには、おおよその行数など、テーブルに関する情報を保持する特別な「情報」テーブルがあります（これも正確ではありません）。トランザクションによる行数）。

于 2008-12-17T15:10:11.270 に答える
8

いいえ、これは一般的な使用例ではありません。私が見たほとんどの行数には、where句が含まれています。

ただし、これが実装されていない主な理由は、行カウンターがマルチユーザー環境での競合の原因になるためです。行が挿入または削除されるたびに、カウンターを更新して、挿入/削除ごとにテーブル全体を効果的にロックする必要があります。

于 2008-12-17T15:09:54.297 に答える
3

MS SQLサーバーでは、テーブルに対してCount（*）を実行すると、常にインデックススキャン（主キーに対して）またはテーブルスキャン（両方とも不良）が実行されます。大きなテーブルの場合、これには時間がかかることがあります。

代わりに、現在のレコード数をほぼ瞬時に表示するための優れたトリックがあります（Microsoftがテーブルを右クリックしてプロパティを選択したときに使用するものと同じです）。

--SQL 2005 or 2008
select sum (spart.rows)
from sys.partitions spart
where spart.object_id = object_id('YourTable')
and spart.index_id < 2

--SQL 2000
select max(ROWS) from sysindexes
where id = object_id('Resolve_Audit')

この数値は、SQLがインデックス統計を更新する頻度によってはわずかにずれている場合がありますが、正確な数値ではなく、球場が必要な場合は、これらはうまく機能します。

于 2008-12-19T17:10:28.650 に答える
3

インデックスまたはテーブルに基づくCOUNT（*）のパフォーマンスは、実際にはセグメントサイズに依存します。1行のみの1GBテーブルを作成できますが、Oracleは割り当てられたスペース全体をスキャンする必要がある場合があります。さらに100万行を挿入しても、最高水準点が変わらなければ、パフォーマンスにまったく影響しない可能性があります。インデックスは同様の方法で機能します。削除のパターンが異なると、インデックス構造に異なる量の空き領域が残り、インデックススキャンのパフォーマンスがO（N）よりも良くなったり悪くなったりする可能性があります。

したがって、理論的にはO（N）です。実際には、それが非常に異なる原因となる可能性のある実装の問題があります。

たとえば、OracleデータウェアハウスのパフォーマンスがO（N）よりも優れている場合があります。特に、オプティマイザーはビットマップインデックスをスキャンでき、ビットマップインデックスのサイズは、bツリーインデックスとは異なり、テーブルのサイズとの関連性が弱いだけです。これは、インデックスサイズをテーブルのサイズ、一意の値の数、テーブル全体での値の分布、および履歴の読み込みパターンに依存させる圧縮方法によるものだと思います。したがって、テーブルの行数を2倍にすると、インデックスのサイズが10％しか増加しない可能性があります。

マテリアライズド・ビューが存在する場合は、要約表を読み取ることによってO（1）を取得することもできます（トリガーはこれを行うための安全でない方法です）。

于 2008-12-17T15:35:56.180 に答える
2

トランザクションエンジンでは、現在のトランザクションに存在する行数を確認する必要があるため、一定の時間ではありません。これには通常、テーブル全体のスキャンが含まれます。

where 句を使用しないで COUNT(*) を最適化することは、データベースが他のことを犠牲にして行うのに特に役立つ最適化ではありません。大きなテーブルのユーザーがそのようなクエリを実行することはめったになく、WHERE 句が存在する場合はまったく役に立ちません。

MySQL の MyISAM は、正確な行数を格納することで「チート」を行いますが、MVCC を持たないため、行がどのトランザクションにあるかを心配する必要がないため、これを行うことしかできません。

于 2008-12-18T22:48:18.303 に答える
1

Oracleの場合、クエリ結果がキャッシュにない限り、通常はO（N）になります。これは、基本的にすべてのブロックを反復するか、インデックスを反復してそれらをカウントする必要があるためです。

于 2008-12-17T14:59:27.330 に答える
1

通常はO（N）です。

このようなクエリに対するO（1）応答が必要な場合は、次のいずれかを使用して簡単に実行できます。

  • クエリをカウントするインデックス付きビュー。
  • カウントを手動で別のテーブルに保存し、トリガーを使用して行カウントを更新します。

例：

CREATE TABLE CountingTable ( Count int )

INSERT CountingTable VALUES(0)

CREATE TRIGGER Counter ON Table FOR INSERT, UPDATE, DELETE AS
BEGIN
   DECLARE @added int, @Removed int
   SET @added = SELECT COUNT(*) FROM inserted
   SET @removed = SELECT COUNT(*) FROM deleted
   UPDATE CountingTable SET Count = Count + @added - @removed
END
于 2008-12-17T15:12:56.660 に答える
0

データベースは、テーブル内の行数を格納し、O（1）を次のように応答できます。 select count(*) From MyTable

しかし、本当に、それは彼らに何の利益をもたらすでしょうか？それからのバリエーション（たとえばselect count(*) from MyTable where Category = 5）は、全表スキャン（またはインデックススキャン）を必要とし、O（N）になります。

于 2008-12-17T15:03:35.043 に答える
0

SQL Serverには（不正確な）ショートカットがあり、テーブルのインデックスなどの特定のオブジェクトのメタデータsys.partitionsのカウントを確認できます。

操作はO（1）ですが、これは単なる見積もりです。

于 2008-12-17T15:11:53.137 に答える
0

どうやらPostgreSQLのO(N):

=> explain select count(*) from tests;
                         QUERY PLAN                              
---------------------------------------------------------------------
Aggregate  (cost=37457.88..37457.89 rows=1 width=0)
  ->  Seq Scan on tests  (cost=0.00..33598.30 rows=1543830 width=0)
(2 rows)

(Seq Scan は、テーブル全体をスキャンする必要があることを意味します)

于 2008-12-18T09:34:08.437 に答える