Как мога да открия и обвързвам промени между стойностите на редовете в SQL таблица?

Намиране на „ToTime“ чрез агрегати вместо присъединяване

Бих искал да споделя една наистина дива заявка, която отнема само 1 сканиране на таблицата с 1 логическо четене. За сравнение, най-добрият друг отговор на страницата, заявката на Саймън Кингстън, отнема 2 сканирания.

На много голям набор от данни (17 408 реда за въвеждане, произвеждащи 8 193 реда с резултати) отнема CPU 574 и време 2645, докато заявката на Simon Kingston отнема CPU 63 820 и време 37 108.

Възможно е с индекси другите заявки на страницата да се представят многократно по-добре, но за мен е интересно да постигна 111x подобрение на процесора и 14x подобрение на скоростта само чрез пренаписване на заявката.

(Моля, обърнете внимание:нямам предвид никакво неуважение към Саймън Кингстън или някой друг; просто съм развълнуван от идеята ми за тази заявка, която да се представи толкова добре. Неговата заявка е по-добра от моята, тъй като нейното представяне е много и всъщност е разбираемо и поддържаемо , за разлика от моя.)

Ето невъзможната заявка. Трудно е да се разбере. Беше трудно да се пише. Но е страхотно. :)

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

Забележка:Това изисква SQL 2008 или по-нова версия. За да работи в SQL 2005, променете клаузата VALUES на SELECT 1 UNION ALL SELECT 2 .

Актуализирана заявка

След като помислих малко за това, разбрах, че изпълнявам две отделни логически задачи едновременно и това направи заявката ненужно сложна:1) изрязване на междинни редове, които нямат отношение към окончателното решение (редове, които не започват нова задача) и 2) изтеглете стойността "ToTime" от следващия ред. Като изпълнявате #1 преди #2, заявката е по-проста и се изпълнява с приблизително половината процесор!

И така, ето опростената заявка, която първо изрязва редовете, които не ни интересуват, след това получава стойността ToTime, използвайки агрегати, а не JOIN. Да, той има 3 функции за прозорец вместо 2, но в крайна сметка поради по-малкото редове (след подрязването на тези, които не ни интересуват) има по-малко работа за вършене:

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;

Тази актуализирана заявка има всички същите проблеми, както представих в моето обяснение, но те са по-лесни за решаване, защото не се занимавам с допълнителните ненужни редове. Виждам също, че Row_Number() / 2 стойност 0 трябваше да изключа и не съм сигурен защо не го изключих от предишната заявка, но във всеки случай това работи перфектно и е невероятно бързо!

Външно приложение подрежда нещата

И накрая, ето версия, която по същество е идентична със заявката на Саймън Кингстън, която според мен е по-лесна за разбиране на синтаксиса.

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;

Ето скрипта за настройка, ако искате да направите сравнение на производителността на по-голям набор от данни:

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

Обяснение

Ето основната идея зад моята заявка.

1. Времената, които представляват превключване, трябва да се появят в два съседни реда, единият за прекратяване на предишната дейност и един за започване на следващата дейност. Естественото решение за това е свързване, така че изходен ред да може да изтегли от собствения си ред (за началния час) и следващия променен ред (за крайния час).

2. Въпреки това, моята заявка постига необходимостта крайните времена да се показват в два различни реда, като се повтаря редът два пъти, с CROSS JOIN (VALUES (1), (2)) . Сега имаме дублирани всички наши редове. Идеята е, че вместо да използваме JOIN за изчисление между колони, ще използваме някаква форма на агрегиране, за да свием всяка желана двойка редове в един.

3. Следващата задача е всеки дублиран ред да се раздели правилно, така че един екземпляр да върви с предишната двойка, а един към следващата двойка. Това се постига с T колоната, ROW_NUMBER() подредени по Time , и след това разделено на 2 (въпреки че го промених, направих DENSE_RANK() за симетрия, тъй като в този случай той връща същата стойност като ROW_NUMBER). За ефективност извърших разделянето в следващата стъпка, така че номерът на реда да може да се използва повторно в друго изчисление (продължете да четете). Тъй като номерът на реда започва от 1 и разделянето на 2 имплицитно се преобразува в int, това има ефект на производство на последователността 0 1 1 2 2 3 3 4 4 ... който има желания резултат:чрез групиране по тази изчислена стойност, тъй като ние също подредихме по Num в номера на реда вече постигнахме, че всички набори след първия се състоят от Num =2 от „предишния“ ред и Num =1 от „следващия“ ред.

4. Следващата трудна задача е да измислим начин да елиминираме редовете, които не ни интересуват, и по някакъв начин да свием началното време на блок в същия ред като крайното време на блок. Това, което искаме, е начин да накараме всеки отделен набор от бягане или ходене да получи собствен номер, за да можем да групираме по него. DENSE_RANK() е естествено решение, но проблемът е, че обръща внимание на всяка стойност в ORDER BY клауза--нямаме синтаксис за изпълнение DENSE_RANK() OVER (PREORDER BY Time ORDER BY Name) така че Time не предизвиква RANK изчисление за промяна, освен при всяка промяна в Name . След известно мислене разбрах, че мога да крехкам малко от логиката зад решението за групирани острови на Ицик Бен-Ган и разбрах, че рангът на редовете е подреден по Time , изваден от ранга на редовете, разделени с Name и подредени по Time , ще даде стойност, която е една и съща за всеки ред в същата група, но различна от другите групи. Общата техника за групирани острови е да се създадат две изчислени стойности, които и двете се издигат в заключена стъпка с редовете като 4 5 6 и 1 2 3 , че при изваждане ще се получи същата стойност (в този примерен случай 3 3 3 като резултат от 4 - 1 , 5 - 2 и 6 - 3 ). Забележка:Първоначално започнах с ROW_NUMBER() за моя N изчисление, но не работи. Правилният отговор беше DENSE_RANK() макар че съжалявам да кажа, че не помня защо стигнах до това по това време и ще трябва да се гмурна отново, за да го разбера. Но така или иначе, това е, което T-N изчислява:число, което може да бъде групирано, за да се изолира всеки „остров“ с едно състояние (или бягане, или ходене).

5. Но това не беше краят, защото има някои бръчки. На първо място, "следващият" ред във всяка група съдържа неправилните стойности за Name , N и T . Заобикаляме това, като избираме от всяка група стойността от Num = 2 ред, когато съществува (но ако не съществува, тогава използваме останалата стойност). Това дава изрази като CASE WHEN NUM = 2 THEN x END :това ще премахне правилно неправилните стойности на "следващия" ред.

6. След известно експериментиране разбрах, че не е достатъчно групирането по T - N само по себе си, тъй като и групите за ходене, и групите за бягане могат да имат една и съща изчислена стойност (в случай на моите примерни данни, предоставени до 17, има две T - N стойности на 6). Но просто групиране по Name също така решава този проблем. Никоя група от „Бягане“ или „Ходене“ няма да има същия брой интервенционни стойности от противоположния тип. Тоест, тъй като първата група започва с „Running“ и има два „Walking“ реда, които се намесват преди следващата „Running“ група, тогава стойността за N ще бъде с 2 по-малка от стойността за T в тази следваща група "Тече". Току-що разбрах, че един от начините да мисля за това е, че T - N изчислението отчита броя на редовете преди текущия ред, които НЕ принадлежат на една и съща стойност "Бягане" или "Ходеща". Някои мисли ще покажат, че това е вярно:ако преминем към третата група "Бягащи", това е само третата група, тъй като има група "Ходеща", която ги разделя, така че тя има различен брой междинни редове, идващи в преди него и поради това, че започва от по-висока позиция, той е достатъчно висок, така че стойностите да не могат да се дублират.

7. И накрая, тъй като нашата последна група се състои само от един ред (няма крайно време и трябва да покажем NULL вместо това) Трябваше да пусна изчисление, което може да се използва, за да се определи дали имаме крайно време или не. Това се постига с Min(Num) израз и след това най-накрая откриване, че когато Min(Num) е 2 (което означава, че нямаме "следващ" ред), тогава показва NULL вместо Max(ToTime) стойност.

Надявам се това обяснение да е от полза за хората. Не знам дали моята техника за „умножаване на редове“ ще бъде като цяло полезна и приложима за повечето автори на SQL заявки в производствени среди поради трудностите при разбирането й и трудността при поддръжката, която със сигурност ще представи на следващия човек, който посети код (реакцията вероятно е „Какво, по дяволите, прави!?!“, последвано от бързо „Време е за пренаписване!“).

Ако сте стигнали дотук, тогава ви благодаря за отделеното време и че ме отдадете на моята малка екскурзия в невероятно-забавна-sql-puzzle-land.

Вижте го сами

А.к.а. симулиране на "ПРЕДВАРИТЕЛНА ПОРЪЧКА ОТ":

Една последна забележка. За да видите как T - N върши работата - и отбелязвайки, че използването на тази част от моя метод може да не е общоприложимо за SQL общността - изпълнете следната заявка към първите 17 реда от примерните данни:

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];

Това дава:

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

Важната част е, че всяка група от "Ходене" или "Бягане" има една и съща стойност за T - N която е различна от всяка друга група със същото име.

Ефективност

Не искам да задълбочавам въпроса, че моята заявка е по-бърза от тази на други хора. Въпреки това, като се има предвид колко поразителна е разликата (когато няма индекси), исках да покажа числата в табличен формат. Това е добра техника, когато е необходима висока производителност на този вид корелация между редове.

Преди стартиране на всяка заявка използвах DBCC FREEPROCCACHE; DBCC DROPCLEANBUFFERS; . Зададох MAXDOP на 1 за всяка заявка, за да премахна сриващите се във времето ефекти на паралелизма. Избрах всеки набор от резултати в променливи, вместо да ги връщам на клиента, така че да измервам само производителността, а не предаването на данни от клиента. На всички заявки са дадени едни и същи клаузи ORDER BY. Всички тестове са използвали 17 408 реда за въвеждане, които дават 8 193 реда с резултати.

Не се показват резултати поради следните хора/причини:

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

Без индекс:

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

С индекс 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

С индекс 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

Така че моралът на историята е:

Подходящите индекси са по-важни от магията на заявките

С подходящия индекс версията на Саймън Кингстън печели като цяло, особено когато включва сложност/поддържаемост на заявката.

Внимавайте добре с този урок! 38k четения всъщност не са толкова много, а версията на Саймън Кингстън работи наполовина по-кратко от моята. Увеличението на скоростта на моята заявка се дължи изцяло на липсата на индекс в таблицата и съпътстващата катастрофална цена, която това даде на всяка заявка, която се нуждае от присъединяване (което моята не направи):пълно сканиране на таблицата Hash Match убива нейната производителност. С индекс, неговата заявка успя да направи вложен цикъл с клъстерно търсене на индекс (известен още като търсене на отметка), което направи нещата наистина бързо.

Интересно е, че само един клъстериран индекс на Time не беше достатъчен. Въпреки че Times бяха уникални, което означава, че се появява само едно име на път, то все пак се нуждаеше от името да бъде част от индекса, за да го използва правилно.

Добавянето на клъстерирания индекс към таблицата, когато е пълен с данни, отне под 1 секунда! Не пренебрегвайте вашите индекси.