Złożoność obliczeniowa zapytania SQL - jest coś takiego ?

Witam,
ostatnio miałem okazję przypomnieć sobie coś na temat złożoności obliczeniowej, pamięciowej podstawowych algorytmów..

Zastanawiam się jednak czy takie pojęcie złożoności ('w myśl notacji duzego O') można zastosować do zapytań SQL, a jeśli tak to jak to liczyć..

dla przykładu:
(są tutaj użyte jakieś podzapytania, złączenia, grupowanie, sortowanie... ale jak to przełożyć na "wzór" złożoności obliczeniowej?)

SELECT sub.* FROM
(
SELECT pivot.* FROM
(
SELECT res.id, res.total, 
SUM(value*(1-abs(sign(numS-1)))) AS val1, 
SUM(value*(1-abs(sign(numS-2)))) AS val2, 
SUM(value*(1-abs(sign(numS-3)))) AS val3, 
SUM(value*(1-abs(sign(numS-4)))) AS val4, 
SUM(value*(1-abs(sign(numS-5)))) AS val5, 
SUM(value*(1-abs(sign(numS-6)))) AS val6, 
SUM(value*(1-abs(sign(numS-7)))) AS val7, 
SUM(value*(1-abs(sign(numS-8)))) AS val8, 
SUM(value*(1-abs(sign(numS-9)))) AS val9, 
SUM(value*(1-abs(sign(numS-10)))) AS val10 
FROM shot  
INNER JOIN res  
ON res.id = shot.id
GROUP BY  id, res.id,
res.p_id, res.total 
) pivot
WHERE (SELECT COUNT(1) FROM res AS t2 WHERE t2.p_id = pivot.p_id AND t2.total > pivot.total AND t2.total ) = 0 
) sub
INNER JOIN res w 
ON w.id = sub.id 
ORDER BY w.total DESC, w.number_10 DESC;

podsumowując, kieruje zapytanie : Jak Wy, odpowiedzielibyście na pytanie złożoności takiego zapytania ?

Należy poprosić optymalizator kosztowy o wyświetlenie planu zapytania, inaczej nic z tego.

Wprawdzie nie da się dokładnie określić bez planu zapytania, jednak zgrubnie można założyć, że:

• projekcja: zwykle jej koszt można pominąć, chyba że używamy jakiś bardzo ciężkich funkcji - ogólnie O(n), gdzie n wielkość wyniku, ale z bardzo małą stałą

• sortowanie / grupowanie: O(n), gdzie n ilość danych do posortowania / pogrupowania; czynnik logarytmiczny zwykle się pomija, ze względu na bardzo dużą podstawę logarytmu i dominowanie operacji we/wy nad CPU; generalnie bardzo, bardzo, kosztowne, wyjątkiem jest jeśli dane mamy już posortowane w dobrej kolejności w jakimś Bdrzewie, wtedy bazy czasem potrafią zauważyć, że sortowanie można pominąć. Tak samo niektóre systemy potrafią "nieco oszukać" i np. jeśli jest ORDER BY...LIMIT..., to nie wykonają sortowania, a selekcję TOP-k, która jest też liniowa względem we/wy, ale ok. 3-5x szybsza.

• filtrowanie: O(N) jeśli nie ma indeksu lub indeks bitmapowy i O(n) jeśli mamy indeks B+Tree lub Hash, gdzie N - ilość wszystkich danych, n - ilość danych, które spełniają warunek. Szybkość indeksu bitmapowego opiera się głównie na bardzo poważnym zmniejszeniu stałej (nawet tysiące razy jeśli indeks cały mieści się w RAM).

• złączenia: w najgorszym przypadku trzeba się nastawić na O(N1 + N2 + n), gdzie N1, N2 wielkości złączanych zbiorów danych, a n wielkość wyniku; złączenia potrafią być szybkie jeśli po jednej stronie mamy mało rekordów do złączenia, a po drugiej jest indeks - wtedy można typowo przyjąć O(n).

• podzapytania skorelowane w WHERE / HAVING np. z użyciem operatora IN: w najgorszym przypadku, jeśli optymalizator nie wyczai jak przepisać na złączenie, O(N1 * N2), gdzie N1, N2 - wielkości odpowiednio zbioru zewnętrznego i wewnętrznego. Jeśli przepisze na złączenie (semijoin), to tak jak złączenie, więc dużo lepiej. Z tego co pamiętam, MySQLa kiedyś bardzo łatwo było takim podzapytaniem skorelowanym zabić, nawet przy bardzo niewielkiej ilości danych.