Вычислительная сложность SQL-запросов

  1. Анализ группового запроса
  2. Постоянная вычислительная сложность O (1) или «Пятый элемент»
  3. суммирование

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

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

Анализ группового запроса

Для тестирования я буду использовать пример, представленный в статье методы измерения производительности запросы. Рассмотрим три варианта запросов, чтобы найти информацию о последнем заказе для каждого клиента. Мы предполагаем, что запрос будет ссылаться только на одну таблицу - dbo.Orders.

ИСПОЛЬЗОВАТЬ N ИЛИ THW IN D GO - Q1 - простое соединение SELECT / * Простое соединение * / o. CustomerId, o. OrderId, o. ShipCountry FROM dbo. Заказы на ВНУТРЕННЕЕ СОЕДИНЕНИЕ (ВЫБЕРИТЕ CustomerID, MAX (OrderID) КАК OrderID FROM dbo. Заказы GROUP BY CustomerID) AS MaxOrd ON o. OrderID = MaxOrd. OrderID; - Q2 - коррелированный подзапрос SubQ *, подзапрос * / CustomerId, OrderId, ShipCountry FROM dbo. Заказы как o1 ГДЕ OrderID = (ВЫБЕРИТЕ МАКС (OrderID) ОТ dbo. Заказы как O2 ГДЕ CustomerID = o1. CustomerID) - Q3 с CROSS APPLY (аналоговый TVF) SELECT / * CROSS APPLY * / CustomerId, OrderId, ShipCountry FROM dbo. Заказы для перекрестного применения (SELECT MAX (OrderID) как MaxOrderID FROM dbo. Заказы как O2 WHERE CustomerID = o. CustomerID) t где o. OrderID = MaxOrderID; GO 100

В ходе испытаний можно было определить, что лучшим решением из предложенного является Вопрос № 1 - Простое соединение.
В ходе испытаний можно было определить, что лучшим решением из предложенного является Вопрос № 1 - Простое соединение
Протестированные запросы, однако, работали на очень небольшом наборе. В таблице dbo.Orders всего 830 записей. Разница в производительности, в этом случае, является результатом лучшего плана реализации Simple JOIN. Два других запроса имеют худший (но один и тот же) план, следовательно, почти идентичный результат.

Оптимизатор запросов, наряду с увеличением количества файлов или распределением данных, может выбрать более выгодный план реализации (если текущий не соответствует определенным критериям). Для дальнейшего тестирования я буду использовать аналогичную таблицу, такую ​​как dbo.Orders (с точки зрения распределения данных CusomerId). Мы будем увеличивать количество заказов (записей), оставляя количество клиентов на одном уровне. Скрипт генерирует и заполняет наш тест dbo.Orders ниже:

ИСПОЛЬЗУЙТЕ ИЛИ THW IN D GO ЕСЛИ OBJECT_ID ('dbo.Orders2') не является нулевым DROP TABLE dbo. Orders2 CREATE TABLE dbo. Orders2 (OrderId INT NOT NULL ПЕРВИЧНАЯ КЛЮЧЕВАЯ ИДЕНТИЧНОСТЬ (1, 1), CustomerID VARCHAR (5), OrdValue decimal (10, 2), ShipCountry varchar (10)) GO - воспроизведение аналоговых индексов, как в Northwind.dbo.Orders CREATE NONCLUSTERED INDEX CustOrd ON [dbo]. [Orders2] (CustomerId ASC) - для запуска 1000 заказов для 100 клиентов. SET NOCOUNT ON DECLARE @i INT SET @i = 0 WHILE @i <1000 НАЧАТЬ ВСТАВИТЬ В dbo. Orders2 (CustomerID, OrdValue, ShipCountry) VALUES (CAST (FLOOR (RAND () * 100) + 1 AS VARCHAR (5)), FLOOR (RAND () * 100000) + 1, НИЖНИЙ (ЛЕВЫЙ (NEWID (), 8) )) SET @i = @i + 1; END

Вначале проверьте, будут ли в нашей тестовой таблице результаты одинаковыми для того же набора - 1000 заказов для 100 клиентов.
Вначале проверьте, будут ли в нашей тестовой таблице результаты одинаковыми для того же набора - 1000 заказов для 100 клиентов
Это похоже - более-менее одинаковые по размеру классы. Simple JOIN работает лучше, чем другие два, идентичные с точки зрения производительности (планы / чтения) запроса.
Посмотрим, как он будет сравнивать эффективность, увеличивая количество записей.

Для этого сценария вы можете увидеть, что в какой-то момент из примерно 40 тыс. Записей все предложенные решения стремятся в одном ритме - в одном и том же плане выполнения. Они предлагают практически одинаковую производительность для больших урожаев. Он тесно связан с вычислительной сложностью алгоритма доступа к данным - он растет линейно (индексное сканирование) по отношению к количеству записей.

Постоянная вычислительная сложность O (1) или «Пятый элемент»

Прорывным решением для нашего сценария может быть запрос, учитывающий это характерное распределение данных в таблице. Фиксированное количество клиентов / группировка объектов и растущее количество заказов. С помощью оконной функции CTE + OVER () мы можем сохранить наш запрос таким, казалось бы, интуитивно понятным способом:

WITH / * Q0 * / customer AS (ВЫБРАТЬ MIN (CustomerId) AS CustomerId ИЗ Orders2 UNION ALL SELECT a. CustomerId FROM (SELECT o. CustomerId, ROW_NUMBER () OVER (ORDER BY o. CustomerId) КАК id_Cust ОТ клиентов cu ВНУТРЕННЕЕ СОЕДИНЕНИЕ o ON o CustomerId> cu. CustomerId) и WHERE a. id_Cust = 1) ВЫБРАТЬ a. * ИЗ ПОЛЬЗОВАТЕЛЕЙ c CROSS APPLY (ВЫБРАТЬ ТОП 1 st. CustomerId, o. OrderId, o. ShipCountry FROM Orders2 o WHERE o. CustomerId = c) CustomerId ORDER BY OrderId desc) a - если имеется более 100 клиентов;) OPTION (MAXRECURSION 0)

Для начала сравните производительность для небольшого стола (1000 заказов, 100 клиентов). Вы можете видеть, что новый запрос «немного выпирает» из классически простых, красивых решений:
Для начала сравните производительность для небольшого стола (1000 заказов, 100 клиентов)
Реальная прибыль видна только в больших наборах, когда предыдущие решения объединяются в космическом направлении, запрос на первый взгляд «przekombinowana» предлагает постоянную (даже при миллионах записей) производительность.

Наконец, вы все еще можете улучшить эти результаты, добавив дополнительный (подходящий для всех этих запросов) индекс:

СОЗДАТЬ ИНДЕКС DemolutionResults НА ДБО. Orders2 (CustomerID, OrderId) IN CLUDE (ShipCountry);

Вычислительная сложность предлагаемого решения растет линейно с количеством клиентов, для которых вам нужно искать последний заказ. Тем не менее, это постоянно для заказов, растущих в этой группе клиентов. Независимо от того, есть ли 10k или 10M!

суммирование

Не всегда возможно достигнуть сложности O (1), и не всегда алгоритм такой сложности (из-за стоимости) будет адекватным решением проблемы (даже небольшие таблицы, представленные здесь). Тем не менее, стоит помнить о будущем запросов, которые могут работать с конкретными, большими наборами, например, статистики измерений устройств.