Proces optymalizacji zapytania, bazuje między innymi na konkretnych zbiorach testowych. Sprawdzamy różne warianty, mierzymy wydajność, a po jakimś czasie…. okazuje się, że wraz z dużym przyrostem danych zapytanie dramatycznie zwalnia. Nie chodzi tylko o kwestie właściwych indeksów czy aktualnych statystyk. Warto zastanowić się nieco bardziej nad docelowym zbiorem, na którym będzie pracować dana kwerenda.

W artykule tym, rozwinę nieco wątek badania wydajności zapytań SQL o czynnik złożoności obliczeniowej i analizy rozkładu danych. Porównamy zapytania doskonale działające dla małych zbiorów, z takimi, które nie mają konkurencji w przypadku dużych tabel.

Analiza kwerendy grupującej

Do testów posłużę się przykładem prezentowanym w artykule dotyczącym metod pomiarów wydajności zapytań. Weźmy pod uwagę trzy wersje kwerend, do wyszukania informacji o najnowszym zleceniu dla każdego z Klientów. Zakładamy odwoływanie się w zapytaniu tylko do jednej tabeli – dbo.Orders.

USE NORTHWIND
GO

-- Q1 - prosty join 
SELECT /* Simple Join */ o.CustomerId, o.OrderId  , o.ShipCountry
FROM dbo.Orders o INNER JOIN 
		( 
		SELECT CustomerID, MAX(OrderID) AS OrderID 
		FROM dbo.Orders 
		GROUP BY CustomerID
		) AS MaxOrd   ON  o.OrderID = MaxOrd.OrderID;

-- Q2 - podzapytanie skorelowane
SELECT /* Correlated SubQ */ CustomerId, OrderId, ShipCountry
FROM dbo.Orders as o1
WHERE  OrderID = (
          SELECT MAX(OrderID) 
          FROM dbo.Orders as O2 
          WHERE CustomerID = o1.CustomerID 
                )

-- Q3 z CROSS APPLY (analogia TVF)
SELECT /* CROSS APPLY */ CustomerId, OrderId, ShipCountry
FROM dbo.Orders o Cross APPLY ( SELECT MAX(OrderID) as MaxOrderID 
          FROM dbo.Orders as O2 
          WHERE CustomerID = o.CustomerID ) t
where o.OrderID = MaxOrderID;
GO 100

W testach udało się ustalić, że najlepszym rozwiązaniem z zaproponowanych, okazało się zapytanie numer 1 – Simple Join.

Testowane kwerendy, działały jednak na bardzo małym zbiorze. W tabeli dbo.Orders jest tylko 830 rekordów. Różnica w wydajności, wynika w tym przypadku z lepszego planu wykonania dla Simple JOINa. Pozostałe dwie kwerendy, posiadają gorszy (ale taki sam) plan, stąd niemal identyczny wynik.

Optymalizator zapytań, wraz ze wzrostem liczebności zbiorów czy rozkładem danych, potrafi wybrać korzystniejszy plan wykonania (jeśli obecny nie spełnia określonych kryteriów). Do dalszych testów, posłużę się analogiczną tabelą jak dbo.Orders (jeśli chodzi o rozkład danych CusomerId). Będziemy zwiększać liczbę zleceń (rekordów), pozostawiając ilość Klientów na tym samym poziomie. Skrypt generujący i zapełniający naszą testową dbo.Orders poniżej :

USE NORTHWIND
GO

IF OBJECT_ID('dbo.Orders2') is not null DROP TABLE dbo.Orders2

CREATE TABLE dbo.Orders2 (
  OrderId INT NOT NULL PRIMARY KEY  IDENTITY(1,1),
  CustomerID VARCHAR(5) ,
  OrdValue decimal(10,2),
  ShipCountry varchar(10)
)
GO
 
-- odtworzenie analogicznych indeksów co w Northwind.dbo.Orders
CREATE NONCLUSTERED INDEX CustOrd ON [dbo].[Orders2]  ( CustomerId ASC)

-- na początek 1000 zleceń dla 100 klientów
SET NOCOUNT ON
DECLARE @i INT
SET @i = 0
WHILE @i < 1000
BEGIN
  INSERT INTO dbo.Orders2 (  CustomerID, OrdValue, ShipCountry)
  VALUES(
	 CAST(FLOOR(RAND()*100)+1 AS VARCHAR(5)), 
	 FLOOR(RAND()*100000)+1 ,
	 LOWER(LEFT(NEWID(),8))
     )
  SET @i = @i+1;
END

Na początek sprawdzenie czy w naszej testowej tabeli, wyniki będą podobne dla analogicznego zbioru – 1000 zamówień dla 100 Klientów.

Jest podobnie – mniej więcej te same klasy wielkości. Simple JOIN wypada znacznie lepiej niż pozostałe dwie, identyczne pod kątem wydajności (planów/odczytów) kwerendy.
Zobaczmy, jak będzie wypadało porównanie wydajności, zwiększając liczbę rekordów.

Widać dla tego scenariusza, że w pewnym momencie, już od około 40k rekordów, wszystkie zaproponowane rozwiązania, pędzą w tym samym rytmie – takim samym planie wykonania. Oferują praktycznie identyczną wydajność w przypadku większych zbiorów. Jest ona ściśle związana ze złożonością obliczeniową algorytmu dostępu do danych – rośnie tu liniowo (skany indeksów) w stosunku do liczby rekordów.

Stała złożoność obliczeniowa O(1) czyli „The Fifth Element”

Przełomowym rozwiązaniem dla naszego scenariusza, może być zapytanie uwzględniające ten charakterystyczny rozkład danych w tabeli. Stała liczba Klientów/obiektów grupujących i rosnąca liczba zamówień. Za pomocą CTE + funkcji okna OVER(), możemy zapisać naszą kwerendę w taki, na pierwszy rzut oka, mało intuicyjny sposób :

WITH /* Q0 */ customers AS
  (  
    SELECT MIN(CustomerId) AS CustomerId
    FROM Orders2
    UNION ALL
    SELECT a.CustomerId
    FROM (	
		SELECT o.CustomerId, ROW_NUMBER() OVER (ORDER BY o.CustomerId) AS id_Cust
		FROM customers cu INNER JOIN Orders2 o ON o.CustomerId > cu.CustomerId
	) a
    WHERE a.id_Cust = 1
  )
SELECT a.*
FROM customers c
CROSS APPLY(
	    SELECT TOP 1 o.CustomerId, o.OrderId, o.ShipCountry
		FROM Orders2 o
		WHERE o.CustomerId = c.CustomerId
		ORDER BY OrderId desc   ) a
-- na wypadek gdyby było więcej niż 100 klientów ;)
OPTION (MAXRECURSION 0)

Na początek porównanie wydajności dla małej tabeli (1000 zamówień, 100 Klientów). Widać że nowa kwerenda „nieco odstaje” od klasycznie prostych, pięknych rozwiązań :

Prawdziwy zysk widać dopiero przy większych zbiorach, w momencie gdy wcześniejsze rozwiązania odpływają razem w jakimś kosmicznym kierunku, kwerenda na pierwszy rzut oka „przekombinowana” oferuje stałą (nawet przy milionach rekordów) wydajność.

Na koniec, można jeszcze poprawić te wyniki, dodając dodatkowy (właściwy dla wszystkich z tych kwerend) indeks :

CREATE INDEX DemolutionResults ON dbo.Orders2 
(CustomerID, OrderId) INCLUDE (ShipCountry);

Złożoność obliczeniowa zaproponowanego rozwiązania rośnie liniowo wraz z liczbą Klientów dla których trzeba wyszukać najnowsze zamówienie. Jest jednak stała, dla rosnącej w ramach tej grupy Klientów, zleceń. Niezależnie czy jest ich 10k czy 10M !

Podsumowanie

Nie zawsze da się osiągnąć złożoność O(1) i nie zawsze algorytm o takiej złożoności (z uwagi na koszt) będzie adekwatnym rozwiązaniem do problemu (choćby przedstawione tutaj małe tabele). Nie mniej jednak, warto mieć na uwadze przyszłość kwerend, które operować mogą na specyficznych, dużych zbiorach np. statystykach pomiarowych urządzeń.