9

我了解计算 SQL 表中行数的最佳方法是 count(*)（或等效的 count(PrimaryKey)）。

  1. 这是 O(1) 吗？
  2. 如果不是，为什么不呢？

为什么不直接实现一个计数器并为这个特定的查询返回它呢？是因为这个查询不是一个常见的用例吗？

如果答案因 SQL 引擎而异，我想听听不同之处 - 但无论如何，我对生产 SQL 引擎中的实际实现感兴趣。

4

11 回答 11

9

在某些RDBM 中，这是 O(1)（最值得注意的是 MySQL），将 AFAIK 放在通常不被接受并被认为是“丑陋的性能黑客”。原因是，如果您有事务（每个真正的 RDBM 都应该有），那么表中的总行数可能等于也可能不等于您可以从当前事务中看到的总数。这就是为什么服务器需要检查哪些行对您的事务实际可见，使其 O(n) 比 O(1) 更多。

如果您想优化获取行数的过程并对近似结果感到满意，大多数 RDBM 都有特殊的“信息”表，其中包含有关表的信息，包括大致的行数（同样，它不是确切的由于事务的行数）。

于 2008-12-17T15:10:11.270 回答
8

不，这不是一个常见的用例。我见过的大多数行数都涉及到一些 where 子句。

未实现的主要原因是行计数器将成为多用户环境中争用的原因。每次插入或删除一行时，计数器都需要更新有效地锁定每个插入/删除的整个表。

于 2008-12-17T15:09:54.297 回答
3

基于索引或表的 COUNT(*) 的性能实际上取决于段大小。你可以有一个只有一行的 1GB 表，但 Oracle 可能仍然需要扫描整个分配的空间。如果不改变高水位线，再插入一百万行可能根本不会影响性能。索引以类似的方式工作，其中不同的删除模式可能会在索引结构中留下不同数量的可用空间，并导致索引扫描提供比 O(N) 更好或更差的性能。

因此，理论上它是 O(N)。在实践中，存在可能导致它非常不同的实施问题。

例如，在某些情况下，Oracle 数据仓库的性能可能优于 O(N)。特别是优化器可以扫描位图索引，位图索引的大小与表的大小只有微弱的关系，这与 b 树索引不同。这是因为压缩方法使索引大小取决于表的大小、唯一值的数量、整个表中值的分布以及我相信的历史加载模式。因此，将表中的行数增加一倍可能只会将索引的大小增加 10%。

在存在物化视图的情况下，您还可能通过读取汇总表得到 O(1)（触发器是一种不安全的做法）。

于 2008-12-17T15:35:56.180 回答
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 回答
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

使用 Informix，在没有 LBAC（基于标签的访问控制）等复杂因素的情况下，SELECT COUNT(*) FROM SomeTable则为 O(1)；它从它维护的控制信息中提取信息。如果有 WHERE 子句或 LBAC，或者表是视图或许多其他因素中的任何一个，那么它不再是 O(1)。

于 2008-12-18T01:32:00.763 回答
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 回答