SELECT Explanation, Example FROM Pro.Knowledge
FacebookRSS

Złożoność obliczeniowa i zapytania SQL do dużych tabel

Stat_smallProces 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.
Zapytania_do_duzych_tabel_01
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.
Zapytania_do_duzych_tabel_02
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.
Zapytania_do_duzych_tabel_03
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ń :
Zapytania_do_duzych_tabel_04
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ść.
Zapytania_do_duzych_tabel_05

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ń.

9 thoughts on “Złożoność obliczeniowa i zapytania SQL do dużych tabel

  1. A czy nie będzie łatwiej i szybciej bez CTE i ROW_NUMBER()?

    SELECT CustomerId, OrderId, ShipCountry
    FROM dbo.Customers c Cross APPLY ( SELECT top(1) OrderId, ShipCountry
              FROM dbo.Orders2 as o 
              WHERE CustomerID = c.CustomerID
              ORDER BY OrderId desc ) t;
  2. W poprzednim komentarzu zapomniałam napisać, że założyłem, że skoro istnieje tabela z zamówieniami Orders to pewnie istnieje też tabela z klientami Customers i są one powiązane.

    • Oczywiście że tak ! Mój przykład dotyczył „pastwienia” się nad kwerendą do jednej tabeli i chciałem pokazać raczej samą ideę na prostym przykładzie… W kontekście złączeń (np. z dbo.Customers) – zaproponowane przez Ciebie rozwiązanie jest zdecydowanie lepsze. Masz od razu dostęp do wszystkich „przedstawicieli” (kluczy) grupujących. Opierając się na właściwych indeksach nie trzeba niczego więcej … tylko index seek :)

      Dzięki za komentarz, trafną uwagę i optymalną kwerendę do tego scenariusza. Pozdrawiam !

    • Ostatnia kwerenda to taki Oraclowy „index skip scan” :) czyli wymuszamy poprzez CTE utworzenie zbioru reprezentatnów a potem b. krótkie skany zakresowe (TOP 1 rekord). Jest to przykład jak uzyć SQL w postaci nie-deklaratywnej a prawie-proceduralnej.

  3. Bardzo fajny artykuł i widać, że poświęciłeś czas na analizę. Mój wniosek jest jednak taki, że praca z bazą, która by w ten sposób przechowuje klientów i zamówienia byłaby katorgą – ale wiem, że nie nim powiem o bazie, że jest nienormalna muszę sprawdzić, w której postaci normalnej się znajduje ;). Na koniec w komentarzach – Michał Komorowski – jest rozwiązanie, które byłoby pierwszym lub drugim, o którym bym pomyślał, gdybym miał do czynienia z „normalną bazą”. W skrócie: wtedy rozwiązanie M. Komorowskiego po prostu mi by się samo nasunęło – zaryzykuję więc stwierdzenie, że jest intuicyjne.

      • Dzięki za komentarz, chodziło o pokazanie innego podejścia. Wiem że nie jest to intuicyjne i tak raczej nie piszemy zapytań, ale jak zaczniesz analizować plan i powiedzmy sposób w który byś oczekiwał jego wykonania – można się przynajmniej starać coś takiego osiągnąć.

Leave a comment

Twój adres email nie zostanie opublikowany.

Uzupełnij równanie (SPAM protection) *