Подсчет строк в таблице SQL в O (1)

Question

Я понимаю, что лучший способ подсчитать количество строк в таблице SQL - это count (*) (или эквивалентно count (PrimaryKey)).

1. Это O (1)?
2. Если нет, то почему?

Почему бы просто не реализовать счетчик и не вернуть его для этого конкретного запроса? Это потому, что этот запрос не является распространенным случаем?

Если ответы различаются в зависимости от механизма SQL, я бы хотел услышать о различиях, но в любом случае меня интересует фактическая реализация в производственных механизмах SQL.

Answer 1

В некоторых RDBM это O (1) (в первую очередь MySQL), для AFAIK его обычно осуждают и считают "уродливым подрывом производительности". Причина в том, что если у вас есть транзакции (которые должна иметь каждая реальная RDBM), общее количество строк в таблице может быть равным или не равным общему количеству , которое вы можете видеть из текущей транзакции . Вот почему серверу необходимо проверить, какие строки на самом деле видны вашей транзакции, делая его больше O (n), чем O (1).

Если вы хотите оптимизировать процесс получения количества строк и удовлетворены приблизительным результатом, большинство СУРБД имеют специальные таблицы «info», которые содержат информацию о таблицах, включая приблизительное количество строк (опять же, это не точное количество строк из-за транзакций).

Answer 2

Нет, это не обычный случай использования. У большинства подсчетов строк, которые я видел, есть условие where.

Основная причина, по которой это не реализовано, заключается в том, что счетчик строк может стать причиной конфликта в многопользовательской среде. Каждый раз, когда строка была вставлена ​​или удалена, счетчик должен будет обновлять, эффективно блокируя всю таблицу для каждой вставки / удаления.

Answer 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 обновляет статистику индекса, но если вам нужен приблизительный показатель, а не точное число, это прекрасно работает.

Answer 4

Производительность COUNT (*) на основе индекса или таблицы действительно зависит от размера сегмента. Вы можете иметь таблицу объемом 1 ГБ, в которой есть только одна строка, но Oracle все равно может сканировать все выделенное пространство. Вставка еще одного миллиона строк может вообще не повлиять на производительность, если она не изменит отметку верхнего уровня. Индексы работают аналогичным образом, когда разные шаблоны удаления могут оставлять разные объемы свободного пространства в структуре индекса и приводить к тому, что сканирование индекса дает лучшую или худшую производительность, чем O (N).

Итак, теоретически это O (N). На практике существуют проблемы с реализацией, которые могут привести к тому, что он будет совсем другим.

Например, в некоторых случаях хранилище данных Oracle может работать быстрее, чем O (N). В частности, оптимизатор может сканировать индекс растрового изображения, а размер индекса растрового изображения слабо связан с размером таблицы, в отличие от индекса b-дерева. Это происходит из-за методологии сжатия, которая делает размер индекса зависимым от размера таблицы, количества уникальных значений, распределения значений по всей таблице, а также, как я полагаю, исторической схемы загрузки. Таким образом, удвоение количества строк в таблице может только увеличить размер индекса на 10%.

При наличии материализованного представления вы также можете получить O (1), читая сводную таблицу (триггер - это небезопасный способ сделать это).

Answer 5

Это не постоянное время, потому что в механизмах транзакций необходимо проверить, сколько строк существует в текущей транзакции, что обычно включает сканирование всей таблицы.

Оптимизация COUNT (*) без предложения where не является особенно полезной оптимизацией для базы данных за счет других вещей; пользователи больших таблиц редко делают такой запрос, и это вообще не поможет, если присутствует предложение WHERE.

MyISAM в MySQL «обманывает», сохраняя точное количество строк, но может делать это только потому, что не имеет MVCC, поэтому не нужно беспокоиться о том, в каких транзакциях строки.

Answer 6

Обычно это 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

Answer 7

Для Oracle это обычно O (N), если результат запроса не находится в кеше, поскольку, по сути, он должен выполнять итерацию всех блоков или индексирование для их подсчета.

Answer 8

Видимо O (N) в 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 означает, что он должен сканировать всю таблицу)

Answer 9

С Informix, в отсутствие усложняющих факторов, таких как LBAC (управление доступом на основе меток), тогда SELECT COUNT(*) FROM SomeTable равно O (1); он извлекает информацию из контрольной информации, которую поддерживает. Если есть предложение WHERE или LBAC, или таблица является представлением или каким-либо другим фактором, то она перестает быть O (1).

Answer 10

Существует (неточный) ярлык в SQL Server, где вы можете посмотреть счетчик в метаданных sys.partitions для определенного объекта, например индекса для таблицы.

Операция O (1), но это только оценка.