Временная сложность встроенных функций SQL, таких как sum, count, avg

Question

Какова временная сложность функции, такой как count, sum, avg или любая другая из встроенных «математических» функций в mysql, sql server, oracle и других?

Можно подумать, что сумма вызова (myColumn) будет линейной.

Но считать (1) нет. Как получилось и каковы сложности в реальном времени?

В идеальном мире я бы хотел, чтобы сумма, средняя и счетная составляли O (1). Но мы не живем в одном из них, не так ли?

Answer 1

Какова временная сложность функции, такой как count, sum, avg или любая другая из встроенных "математических" функций в mysql, sql server, oracle и других?

• В MySQL с MyISAM, COUNT(*) без GROUP BY - O(1) (постоянная)

  Хранится в таблице метаданных.

• Во всех системах MAX и MIN в индексированных выражениях без GROUP BY равны O(log(n)) (логарифмическая).

  Они выбираются с помощью одного индекса поиска.

• Агрегатные функции: O(n) (линейные), при использовании без GROUP BY или GROUP BY используются HASH

• Агрегатными функциями являются O(n log(n)), когда GROUP BY использует SORT.

Все значения должны быть получены, рассчитаны и сохранены в переменных состояния (которые могут храниться в хеш-таблице).

Кроме того, при использовании SORT они также должны быть отсортированы.

Answer 2

В SQL сложность математических функций агрегатов совершенно не имеет значения. Единственное, что действительно имеет значение, - это сложность доступа к данным: какой путь доступа выбран (сканирование таблицы, сканирование диапазона индекса, поиск по индексу и т. Д.) И сколько страниц прочитано. Могут быть небольшие различия во внутренних компонентах каждого агрегата, но все они работают примерно одинаково (продолжайте работать состояние и вычисляйте агрегирующее выполнение для каждого входного значения), и существует абсолютно NO агрегат, который смотрит на вход в два раза, поэтому все они O (n) как внутренняя реализация, где 'n' - количество записей, поданных в агрегат (не обязательно количество записей в таблице!).

Некоторые агрегаты имеют внутренние ярлыки, например. COUNT (*) может возвращать счетчик из метаданных в некоторых системах, если это возможно.

Answer 3

Примечание: это предположение, основанное на моем понимании того, как работают планировщики SQL-запросов, и оно может быть не совсем точным.

Я считаю, что все агрегатные функции или, по крайней мере, "математические" функции, которые вы называете выше, должны быть O (n). Запрос будет выполнен примерно следующим образом:

1. Выборка строк, соответствующих предикатам соединения и фильтрам (т. Е. "Предложение WHERE")
2. Создание групп строк в соответствии с предложением GROUP BY. Одна группа строк создается для запросов без GROUP BY
3. Для каждой группы строк примените статистическую функцию к строкам в группе. Для таких вещей, как SUM, AVG, MIN, MAX, а также для нечисловых функций, таких как CONCAT, существуют простые алгоритмы O (n), и я подозреваю, что они используются. Создайте одну строку в выходном наборе для каждой группы строк, созданной на шаге № 2
4. Если присутствует предикат HAVING, отфильтруйте выходные строки, используя этот предикат

Обратите внимание, однако, что, хотя агрегатными функциями являются O (n), операция может не выполняться. Если вы создаете запрос, который декартово присоединяет таблицу к себе, вы будете искать минимум O (n * n) только для создания начального набора строк (шаг # 1). Сортировка для создания групп строк (шаг № 2) может быть O (n lg n) и может потребовать дискового пространства для операции сортировки (в отличие только от операции в памяти), поэтому ваш запрос может все еще работать плохо, если вы манипулируя многими рядами.

Answer 4

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