tabla - sql contar registros agrupados

Contar filas en una tabla SQL en O(1)

Question

Entiendo que la mejor manera de contar el número de filas en una tabla SQL es el recuento (*) (o conteo equivalente (clave principal)).

1. ¿Es esto O (1)?
2. ¿Si no, porque no?

¿Por qué no simplemente implementar un contador y devolverlo para esta consulta específica? ¿Es porque esta consulta no es un caso de uso común?

Si las respuestas varían según el motor SQL, me gustaría escuchar las diferencias, pero en cualquier caso, estoy interesado en la implementación real en los motores SQL de producción.

Answer 1

En algunos RDBM esto es O (1) (más notablemente MySQL), poner AFAIK generalmente es mal visto y considerado un "hack de rendimiento feo". La razón es que si tiene transacciones (que cada RDBM real debería tener), el número total de filas en la tabla podría o no ser igual al número total que puede ver en la transacción actual . Esta es la razón por la que el servidor necesita verificar qué filas son realmente visibles para su transacción, por lo que es más O (n) que O (1).

Si desea optimizar el proceso de obtener el número de filas y está satisfecho con un resultado aproximado, la mayoría de las RDBM tienen tablas de "información" especiales que contienen información sobre las tablas, incluido el número aproximado de filas (una vez más, no es exactamente número de filas debido a las transacciones).

Answer 2

Hay un acceso directo (inexacto) en SQL Server donde puede ver el recuento en las particiones de sys.datos de metadatos para un objeto en particular, como un índice en una tabla.

La operación es O (1), pero es solo una estimación.

Answer 3

No, este no es un caso de uso común. La mayoría de los recuentos de filas que he visto tienen alguna cláusula en cuestión.

La principal razón por la que esto no se implementa es que el contador de filas sería una causa de contención en un entorno de usuarios múltiples. Cada vez que se insertaba o eliminaba una fila, el contador necesitaría una actualización que bloqueara eficazmente toda la tabla para cada inserción / eliminación.

Answer 4

Normalmente es O (N).

Si se necesita una respuesta O (1) a dicha consulta, puede hacerlo fácilmente usando:

• Una vista indizada que cuenta la consulta.
• Almacenar recuento manualmente en otra tabla y actualizar el recuento de filas con un desencadenador:

Ejemplo:

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

Answer 5

Para Oracle, generalmente es O (N) a menos que el resultado de la consulta esté en caché, ya que esencialmente tiene que iterar todos los bloques o iterar el índice para contarlos.

Answer 6

Una base de datos podría almacenar el número de filas en una tabla y responder O (1) para select count(*) From MyTable

Pero, realmente, ¿de qué serviría eso? Cualquier variación de eso (digamos select count(*) from MyTable where Category = 5 ) requeriría un escaneo de tabla completo (o escaneo de índice) y sería O (N).

Answer 7

Aparentemente O (N) en PostgreSQL:

=> 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 significa que debe escanear toda la tabla)

Answer 8

Con Informix, en ausencia de factores complicados como LBAC (control de acceso basado en etiquetas), entonces SELECT COUNT(*) FROM SomeTable es O (1); extrae la información de la información de control que mantiene. Si hay una cláusula WHERE o LBAC o la tabla es una vista o cualquiera de un número de otros factores, entonces deja de ser O (1).

Answer 9

El rendimiento de un COUNT (*) basado en un índice o en una tabla realmente depende del tamaño del segmento. Puede tener una tabla de 1 GB que solo tenga una sola fila, pero es posible que Oracle tenga que escanear todo el espacio asignado. Insertar otro millón de filas podría no afectar el rendimiento en absoluto si no altera la marca de marea alta. Los índices funcionan de manera similar, donde los diferentes patrones de eliminaciones pueden dejar diferentes cantidades de espacio libre en la estructura del índice y causar que los escaneos de índice den mejores o peores resultados que O (N).

Entonces, teóricamente es O (N). En la práctica, hay problemas de imposición que pueden causar que sea muy diferente.

Por ejemplo, hay algunos casos en los que un almacén de datos de Oracle podría ofrecer un rendimiento mejor que O (N). En particular, el optimizador podría escanear un índice de mapa de bits, y el tamaño de un índice de mapa de bits solo está débilmente relacionado con el tamaño de la tabla, a diferencia de un índice de árbol b. Esto se debe a la metodología de compresión que hace que el tamaño del índice dependa del tamaño de la tabla, el número de valores únicos, la distribución de valores en toda la tabla y el patrón de carga histórica, como creo. Por lo tanto, doblar el número de filas en la tabla solo podría aumentar el tamaño del índice en un 10%.

En presencia de una vista materializada, también puede obtener O (1) leyendo una tabla de resumen (un activador es una forma insegura de hacerlo).

Answer 10

No es un tiempo constante, porque en los motores transaccionales necesita verificar cuántas filas existen en la transacción actual, lo que generalmente implica un escaneo de tabla completo.

Optimizar COUNT (*) sin cláusula where no es una optimización particularmente útil para una base de datos a expensas de otras cosas; los usuarios de tablas grandes raramente hacen tal consulta y no ayudaría en absoluto si hubiera una cláusula WHERE presente.

MyISAM en MySQL "hace trampa" al almacenar el recuento exacto de filas, pero solo puede hacerlo porque no tiene MVCC, por lo tanto, no tiene que preocuparse por las transacciones en las que se encuentran las filas.

Answer 11

En el servidor MS SQL, hacer un recuento (*) en una tabla siempre realiza un escaneo de índice (en la clave principal) o un escaneo de tabla (ambos malos). Para tablas grandes, esto puede tomar un tiempo.

En cambio, hay un buen truco para mostrar el número actual de registros casi al instante (el mismo que usa Microsoft al hacer clic derecho en la tabla y seleccionar propiedades):

--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'')

Este número puede variar ligeramente dependiendo de la frecuencia con la que SQL actualice las estadísticas del índice, pero si necesita un estadio, y no un número exacto, funcionan muy bien.