Jak wykryć i powiązać zmiany między wartościami wierszy w tabeli SQL?

Znajdowanie „ToTime” przez agregaty zamiast złączenia

Chciałbym udostępnić naprawdę dzikie zapytanie, które wykonuje tylko 1 skanowanie tabeli z 1 logicznym odczytem. Dla porównania, najlepsza inna odpowiedź na stronie, zapytanie Simona Kingstona, zajmuje 2 skany.

W przypadku bardzo dużego zestawu danych (17 408 wierszy wejściowych, co daje 8193 wierszy wyników) zajmuje CPU 574 i czas 2645, podczas gdy zapytanie Simona Kingstona zajmuje CPU 63 820 i czas 37 108.

Możliwe, że z indeksami inne zapytania na stronie mogłyby działać wielokrotnie lepiej, ale interesuje mnie osiągnięcie 111-krotnej poprawy procesora i 14-krotnej poprawy szybkości poprzez przepisanie zapytania.

(Uwaga:nie mam na myśli żadnego braku szacunku dla Simona Kingstona ani nikogo innego; jestem po prostu podekscytowany moim pomysłem na to, aby to zapytanie tak dobrze się rozwinęło. Jego zapytanie jest lepsze niż moje, ponieważ jego wydajność jest duża i faktycznie jest zrozumiała i łatwa do utrzymania , w przeciwieństwie do mojego.)

Oto niemożliwe zapytanie. Trudno to zrozumieć. Trudno było pisać. Ale to jest niesamowite. :)

WITH Ranks AS (
   SELECT
      T = Dense_Rank() OVER (ORDER BY Time, Num),
      N = Dense_Rank() OVER (PARTITION BY Name ORDER BY Time, Num),
      *
   FROM
      #Data D
      CROSS JOIN (
         VALUES (1), (2)
      ) X (Num)
), Items AS (
   SELECT
      FromTime = Min(Time),
      ToTime = Max(Time),
      Name = IsNull(Min(CASE WHEN Num = 2 THEN Name END), Min(Name)),
      I = IsNull(Min(CASE WHEN Num = 2 THEN T - N END), Min(T - N)),
      MinNum = Min(Num)
   FROM
      Ranks
   GROUP BY
      T / 2
)
SELECT
   FromTime = Min(FromTime),
   ToTime = CASE WHEN MinNum = 2 THEN NULL ELSE Max(ToTime) END,
   Name
FROM Items
GROUP BY
   I, Name, MinNum
ORDER BY
   FromTime

Uwaga:wymaga to SQL 2008 lub nowszego. Aby działała w SQL 2005, zmień klauzulę VALUES na SELECT 1 UNION ALL SELECT 2 .

Zaktualizowane zapytanie

Po chwili zastanowienia zdałem sobie sprawę, że realizuję jednocześnie dwa oddzielne zadania logiczne, co niepotrzebnie komplikowało zapytanie:1) wycinamy wiersze pośrednie, które nie mają wpływu na ostateczne rozwiązanie (wiersze, które się nie zaczynają nowe zadanie) i 2) pociągnij wartość „ToTime” z następnego wiersza. Wykonując numer 1 przed #2, zapytanie jest prostsze i działa przy około połowie procesora!

Oto uproszczone zapytanie, które najpierw usuwa wiersze, na których nam nie zależy, a potem następnie pobiera wartość ToTime przy użyciu agregatów, a nie JOIN. Tak, ma 3 funkcje okienkowe zamiast 2, ale ostatecznie z powodu mniejszej liczby wierszy (po wycięciu tych, na których nam nie zależy) ma mniej pracy do wykonania:

WITH Ranks AS (
   SELECT
      Grp =
         Row_Number() OVER (ORDER BY Time)
         - Row_Number() OVER (PARTITION BY Name ORDER BY Time),
      [Time], Name
   FROM #Data D
), Ranges AS (
   SELECT
      Result = Row_Number() OVER (ORDER BY Min(R.[Time]), X.Num) / 2,
      [Time] = Min(R.[Time]),
      R.Name, X.Num
   FROM
      Ranks R
      CROSS JOIN (VALUES (1), (2)) X (Num)
   GROUP BY
      R.Name, R.Grp, X.Num
)
SELECT
   FromTime = Min([Time]),
   ToTime = CASE WHEN Count(*) = 1 THEN NULL ELSE Max([Time]) END,
   Name = IsNull(Min(CASE WHEN Num = 2 THEN Name ELSE NULL END), Min(Name))
FROM Ranges R
WHERE Result > 0
GROUP BY Result
ORDER BY FromTime;

To zaktualizowane zapytanie ma te same problemy, które przedstawiłem w moim wyjaśnieniu, jednak są one łatwiejsze do rozwiązania, ponieważ nie mam do czynienia z dodatkowymi niepotrzebnymi wierszami. Widzę też, że Row_Number() / 2 wartość 0 Musiałem wykluczyć i nie jestem pewien, dlaczego nie wykluczyłem go z poprzedniego zapytania, ale w każdym razie działa to doskonale i jest niesamowicie szybkie!

Zewnętrzne zastosowanie porządku rzeczy w górę

Na koniec, oto wersja zasadniczo identyczna z zapytaniem Simona Kingstona, która moim zdaniem jest łatwiejsza do zrozumienia.

SELECT
   FromTime = Min(D.Time),
   X.ToTime,
   D.Name
FROM
   #Data D
   OUTER APPLY (
      SELECT TOP 1 ToTime = D2.[Time]
      FROM #Data D2
      WHERE
         D.[Time] < D2.[Time]
         AND D.[Name] <> D2.[Name]
      ORDER BY D2.[Time]
   ) X
GROUP BY
   X.ToTime,
   D.Name
ORDER BY
   FromTime;

Oto skrypt instalacyjny, jeśli chcesz dokonać porównania wydajności na większym zestawie danych:

CREATE TABLE #Data (
    RecordId int,
    [Time]  int,
    Name varchar(10)
);
INSERT #Data VALUES
    (1, 10, 'Running'),
    (2, 18, 'Running'),
    (3, 21, 'Running'),
    (4, 29, 'Walking'),
    (5, 33, 'Walking'),
    (6, 57, 'Running'),
    (7, 66, 'Running'),
    (8, 77, 'Running'),
    (9, 81, 'Walking'),
    (10, 89, 'Running'),
    (11, 93, 'Walking'),
    (12, 99, 'Running'),
    (13, 107, 'Running'),
    (14, 113, 'Walking'),
    (15, 124, 'Walking'),
    (16, 155, 'Walking'),
    (17, 178, 'Running');
GO
insert #data select recordid + (select max(recordid) from #data), time + (select max(time) +25 from #data), name from #data
GO 10

Wyjaśnienie

Oto podstawowa idea mojego zapytania.

1. Czasy reprezentujące przełącznik muszą pojawić się w dwóch sąsiednich rzędach, jeden do zakończenia poprzedniej czynności, a drugi do rozpoczęcia następnej czynności. Naturalnym rozwiązaniem tego problemu jest sprzężenie, dzięki któremu wiersz wyjściowy może pobrać z własnego wiersza (na czas rozpoczęcia) i następna zmieniona wiersz (dla czasu zakończenia).

2. Jednak moja kwerenda spełnia potrzebę, aby czasy końcowe pojawiały się w dwóch różnych wierszach, powtarzając wiersz dwukrotnie za pomocą CROSS JOIN (VALUES (1), (2)) . Mamy teraz zduplikowane wszystkie nasze wiersze. Pomysł polega na tym, że zamiast używać JOIN do wykonywania obliczeń w kolumnach, użyjemy jakiejś formy agregacji, aby zwinąć każdą pożądaną parę wierszy w jeden.

3. Następnym zadaniem jest prawidłowe dzielenie każdego zduplikowanego wiersza, tak aby jedna instancja pasowała do poprzedniej pary, a druga do następnej pary. Odbywa się to za pomocą kolumny T, ROW_NUMBER() uporządkowane według Time , a następnie podzielone przez 2 (chociaż zmieniłem to na DENSE_RANK() dla symetrii, ponieważ w tym przypadku zwraca tę samą wartość co ROW_NUMBER). Dla wydajności dokonałem podziału w następnym kroku, aby numer wiersza mógł zostać ponownie wykorzystany w innym obliczeniu (czytaj dalej). Ponieważ numer wiersza zaczyna się od 1, a dzielenie przez 2 niejawnie konwertuje na int, skutkuje to powstaniem sekwencji 0 1 1 2 2 3 3 4 4 ... który ma pożądany wynik:grupując według tej obliczonej wartości, ponieważ uporządkowaliśmy również według Num w numerze wiersza osiągnęliśmy teraz, że wszystkie zestawy po pierwszym składają się z Num =2 z „poprzedniego” wiersza i Num =1 z „następnego” wiersza.

4. Kolejnym trudnym zadaniem jest wymyślenie sposobu na wyeliminowanie wierszy, na których nam nie zależy i jakoś zwinięcie czasu rozpoczęcia bloku do tego samego wiersza, co czas zakończenia bloku. To, czego chcemy, to sposób, aby każdy oddzielny zestaw Bieganie lub Chodzenie otrzymał własny numer, abyśmy mogli go pogrupować. DENSE_RANK() jest naturalnym rozwiązaniem, ale problemem jest to, że zwraca uwagę na każdą wartość w ORDER BY klauzula -- nie mamy składni do wykonania DENSE_RANK() OVER (PREORDER BY Time ORDER BY Name) tak, że Time nie powoduje RANK obliczenia do zmiany z wyjątkiem każdej zmiany w Name . Po chwili namysłu zdałem sobie sprawę, że mogę trochę poszukać logiki stojącej za rozwiązaniem zgrupowanych wysp Itzika Ben-Gana i doszedłem do wniosku, że ranga wierszy uporządkowana według Time , odejmowane od pozycji wierszy podzielonych przez Name i uporządkowane według Time , da wartość, która byłaby taka sama dla każdego wiersza w tej samej grupie, ale różna od innych grup. Ogólna technika grupowanych wysp polega na utworzeniu dwóch obliczonych wartości, które rosną w lockstep z wierszami, takimi jak 4 5 6 i 1 2 3 , że po odjęciu da tę samą wartość (w tym przykładzie 3 3 3 jako wynik 4 - 1 , 5 - 2 i 6 - 3 ). Uwaga:początkowo zacząłem od ROW_NUMBER() dla mojego N obliczenia, ale to nie działało. Prawidłowa odpowiedź to DENSE_RANK() chociaż przykro mi to mówić, że nie pamiętam, dlaczego wtedy to doszedłem do wniosku, i musiałbym ponownie zanurkować, aby to rozgryźć. Ale w każdym razie to właśnie T-N oblicza:liczba, którą można pogrupować, aby wyodrębnić każdą „wyspę” o jednym statusie (bieganie lub spacer).

5. Ale to nie był koniec, bo pojawiły się zmarszczki. Przede wszystkim wiersz „następny” w każdej grupie zawiera nieprawidłowe wartości dla Name , N i T . Obchodzimy to, wybierając z każdej grupy wartość z Num = 2 wiersz, gdy istnieje (ale jeśli nie, to używamy pozostałej wartości). Daje to wyrażenia takie jak CASE WHEN NUM = 2 THEN x END :spowoduje to prawidłowe usunięcie nieprawidłowych wartości „następnego” wiersza.

6. Po kilku eksperymentach zdałem sobie sprawę, że nie wystarczy pogrupować według T - N przez siebie, ponieważ obie grupy Walking i Running mogą mieć tę samą obliczoną wartość (w przypadku moich przykładowych danych dostarczonych do 17, są dwa T - N wartości 6). Ale po prostu grupuj według Name jak również rozwiązuje ten problem. Żadna grupa „Bieganie” lub „Chodzenie” nie będzie miała takiej samej liczby interweniujących wartości z przeciwnego typu. Oznacza to, że ponieważ pierwsza grupa zaczyna się od „Uruchomiony”, a przed następną grupą „Uruchomiony” znajdują się dwa wiersze „Chodzenie”, wartość dla N będzie o 2 mniejsza niż wartość dla T w następnej grupie „Bieganie”. Właśnie zdałem sobie sprawę, że jednym ze sposobów myślenia o tym jest to, że T - N obliczenie zlicza liczbę wierszy przed bieżącym wierszem, które NIE należą do tej samej wartości „Bieganie” lub „Walking”. Pewna myśl pokaże, że to prawda:jeśli przejdziemy do trzeciej grupy „Bieganie”, będzie to tylko trzecia grupa, ponieważ dzieli je grupa „Chodząca”, więc ma ona inną liczbę wchodzących rzędów przed nim i ze względu na to, że zaczyna się na wyższej pozycji, jest wystarczająco wysoki, aby nie można było zduplikować wartości.

7. Wreszcie, ponieważ nasza końcowa grupa składa się tylko z jednego wiersza (nie ma czasu zakończenia i musimy wyświetlić NULL zamiast tego) musiałem dorzucić obliczenia, które można wykorzystać do ustalenia, czy mieliśmy czas zakończenia, czy nie. Odbywa się to za pomocą Min(Num) wyrażenie, a następnie w końcu wykrycie, że gdy Min(Num) wynosi 2 (co oznacza, że ​​nie mamy "następnego" wiersza), a następnie wyświetla NULL zamiast Max(ToTime) wartość.

Mam nadzieję, że to wyjaśnienie przyda się ludziom. Nie wiem, czy moja technika „mnożenia wierszy” będzie ogólnie użyteczna i ma zastosowanie do większości twórców zapytań SQL w środowiskach produkcyjnych z powodu trudności w zrozumieniu jej i trudności w utrzymaniu, które z pewnością przyniesie następnej osobie odwiedzającej kod (reakcja to prawdopodobnie „Co to u licha robi!?!”, a następnie szybkie „Czas na przepisanie!”).

Jeśli dotarłeś tak daleko, dziękuję Ci za poświęcony czas i za umożliwienie mi mojej małej wycieczki do niesamowicie-zabawnej-krainy-puzzli.

Zobacz to sam

Znany jako. symulowanie „PREORDER BY”:

Ostatnia uwaga. Aby zobaczyć, jak T - N wykona zadanie — i zauważ, że użycie tej części mojej metody może ogólnie nie mieć zastosowania w społeczności SQL — uruchom następujące zapytanie względem pierwszych 17 wierszy przykładowych danych:

WITH Ranks AS (
   SELECT
      T = Dense_Rank() OVER (ORDER BY Time),
      N = Dense_Rank() OVER (PARTITION BY Name ORDER BY Time),
      *
   FROM
      #Data D
)
SELECT
   *,
   T - N
FROM Ranks
ORDER BY
   [Time];

To daje:

RecordId    Time Name       T    N    T - N
----------- ---- ---------- ---- ---- -----
1           10   Running    1    1    0
2           18   Running    2    2    0
3           21   Running    3    3    0
4           29   Walking    4    1    3
5           33   Walking    5    2    3
6           57   Running    6    4    2
7           66   Running    7    5    2
8           77   Running    8    6    2
9           81   Walking    9    3    6
10          89   Running    10   7    3
11          93   Walking    11   4    7
12          99   Running    12   8    4
13          107  Running    13   9    4
14          113  Walking    14   5    9
15          124  Walking    15   6    9
16          155  Walking    16   7    9
17          178  Running    17   10   7

Ważną częścią jest to, że każda grupa „Chodzenie” lub „Bieganie” ma tę samą wartość dla T - N która różni się od innych grup o tej samej nazwie.

Wydajność

Nie chcę mówić o tym, że moje zapytanie jest szybsze niż zapytania innych osób. Jednak biorąc pod uwagę, jak uderzająca jest różnica (gdy nie ma indeksów), chciałem pokazać liczby w formie tabeli. Jest to dobra technika, gdy potrzebna jest wysoka wydajność tego rodzaju korelacji między wierszami.

Przed uruchomieniem każdego zapytania użyłem DBCC FREEPROCCACHE; DBCC DROPCLEANBUFFERS; . Ustawiam MAXDOP na 1 dla każdego zapytania, aby usunąć efekty paralelizmu zachodzące w czasie. Wybrałem każdy zestaw wyników do zmiennych zamiast zwracać je klientowi, aby mierzyć tylko wydajność, a nie transmisję danych klienta. Wszystkie zapytania otrzymały te same klauzule ORDER BY. We wszystkich testach wykorzystano 17 408 wierszy wejściowych, uzyskując 8193 wiersze wyników.

Brak wyników dla następujących osób/przyczyn:

RichardTheKiwi *Could not test--query needs updating*
ypercube       *No SQL 2012 environment yet :)*
Tim S          *Did not complete tests within 5 minutes*

Bez indeksu:

               CPU         Duration    Reads       Writes
               ----------- ----------- ----------- -----------
ErikE          344         344         99          0
Simon Kingston 68672       69582       549203      49

Z indeksem CREATE UNIQUE CLUSTERED INDEX CI_#Data ON #Data (Time); :

               CPU         Duration    Reads       Writes
               ----------- ----------- ----------- -----------
ErikE          328         336         99          0
Simon Kingston 70391       71291       549203      49          * basically not worse

Z indeksem CREATE UNIQUE CLUSTERED INDEX CI_#Data ON #Data (Time, Name); :

               CPU         Duration    Reads       Writes
               ----------- ----------- ----------- -----------
ErikE          375         414         359         0           * IO WINNER
Simon Kingston 172         189         38273       0           * CPU WINNER

Morał tej historii jest następujący:

Odpowiednie indeksy są ważniejsze niż kreatory zapytań

Z odpowiednim indeksem, wersja Simona Kingstona wygrywa ogólnie, zwłaszcza jeśli uwzględnia złożoność zapytań/możliwość utrzymania.

Zważcie na tę lekcję! 38 tys. odczytów to naprawdę niewiele, a wersja Simona Kingstona była o połowę krótsza od mojej. Wzrost szybkości mojego zapytania był całkowicie spowodowany brakiem indeksu w tabeli, a towarzyszący temu katastrofalny koszt spowodował każde zapytanie wymagające sprzężenia (którego moje nie wymagało):pełne skanowanie tabeli Hash Match zabija jego wydajność. Dzięki indeksowi jego zapytanie było w stanie wykonać zagnieżdżoną pętlę z klastrowym wyszukiwaniem indeksu (tzw. wyszukiwaniem zakładki), co naprawdę szybko.

Interesujące jest to, że sam wskaźnik klastrowy dotyczący czasu nie wystarczył. Mimo że czasy były unikatowe, co oznacza, że ​​w danym momencie wystąpiło tylko jedno Imię, nadal potrzebowało Nazwy, która była częścią indeksu, aby móc ją właściwie wykorzystać.

Dodanie indeksu klastrowego do tabeli przy zapełnieniu danych zajęło mniej niż 1 sekundę! Nie zaniedbuj swoich indeksów.