Jak mohu zjistit a svázat změny mezi hodnotami řádků v tabulce SQL?

Hledání „ToTime“ pomocí agregátů namísto spojení

Rád bych se podělil o opravdu divoký dotaz, který zabere pouze 1 skenování tabulky s 1 logickým čtením. Pro srovnání, nejlepší další odpověď na stránce, dotaz Simona Kingstona, trvá 2 skenování.

Na velmi velké množině dat (17 408 vstupních řádků, což vytváří 8 193 řádků výsledků) to vyžaduje CPU 574 a čas 2645, zatímco dotaz Simona Kingstona zabírá CPU 63 820 a čas 37 108.

Je možné, že s indexy by ostatní dotazy na stránce mohly fungovat mnohonásobně lépe, ale je pro mě zajímavé dosáhnout 111x zlepšení CPU a 14x zvýšení rychlosti pouhým přepsáním dotazu.

(Všimněte si prosím:Nemám na mysli vůbec žádnou neúctu k Simonu Kingstonovi nebo komukoli jinému; jsem prostě nadšený z mého nápadu na tento dotaz, který se tak dobře posouvá. Jeho dotaz je lepší než můj, protože jeho výkon je dostatečný a ve skutečnosti je srozumitelný a udržovatelný. , na rozdíl od mého.)

Zde je nemožný dotaz. Je těžké to pochopit. Bylo těžké psát. Ale je to úžasné. :)

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

Poznámka:To vyžaduje SQL 2008 nebo vyšší. Aby to fungovalo v SQL 2005, změňte klauzuli VALUES na SELECT 1 UNION ALL SELECT 2 .

Aktualizovaný dotaz

Poté, co jsem se nad tím trochu zamyslel, jsem si uvědomil, že provádím dva samostatné logické úkoly současně, a to zbytečně zkomplikovalo dotaz:1) odřízněte meziřádky, které nemají žádný vliv na konečné řešení (řádky, které nezačínají nový úkol) a 2) vytáhněte hodnotu "ToTime" z dalšího řádku. Provedením č. 1 před #2, dotaz je jednodušší a funguje s přibližně polovičním CPU!

Zde je tedy zjednodušený dotaz, který nejprve ořízne řádky, které nás nezajímají, pak získá hodnotu ToTime pomocí agregátů spíše než JOIN. Ano, má 3 okenní funkce místo 2, ale nakonec kvůli menšímu počtu řádků (po ořezání těch, o které se nestaráme) má méně práce:

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;

Tento aktualizovaný dotaz má všechny stejné problémy, jaké jsem uvedl ve svém vysvětlení, je však snazší je vyřešit, protože se nezabývám dalšími nepotřebnými řádky. Také vidím, že Row_Number() / 2 hodnotu 0 jsem musel vyloučit a nejsem si jistý, proč jsem to nevyloučil z předchozího dotazu, ale v každém případě to funguje perfektně a je to úžasně rychlé!

Vnější aplikace Tidies Things Up

Konečně, zde je verze v zásadě identická s dotazem Simona Kingstona, o které si myslím, že je srozumitelnější.

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;

Zde je instalační skript, pokud chcete provést srovnání výkonu na větší sadě dat:

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

Vysvětlení

Zde je základní myšlenka mého dotazu.

1. Časy, které představují přepnutí, se musí objevit ve dvou sousedních řádcích, jeden pro ukončení předchozí aktivity a druhý pro zahájení další aktivity. Přirozeným řešením je spojení, takže výstupní řádek může vytáhnout ze svého vlastního řádku (pro počáteční čas) a další se změnil řádek (pro čas ukončení).

2. Můj dotaz však splňuje potřebu, aby se časy ukončení objevily ve dvou různých řádcích, a to dvojitým opakováním řádku pomocí CROSS JOIN (VALUES (1), (2)) . Nyní máme všechny naše řádky duplikované. Myšlenka je taková, že místo použití JOIN k výpočtu napříč sloupci použijeme nějakou formu agregace ke sbalení každého požadovaného páru řádků do jednoho.

3. Dalším úkolem je správně rozdělit každý duplicitní řádek tak, aby jedna instance šla s předchozí dvojicí a jedna s druhou dvojicí. Toho je dosaženo pomocí sloupce T, ROW_NUMBER() seřazené podle Času , a pak děleno 2 (i když jsem to změnil na DENSE_RANK() pro symetrii, protože v tomto případě vrací stejnou hodnotu jako ROW_NUMBER). Pro efektivitu jsem v dalším kroku provedl dělení, aby bylo možné číslo řádku znovu použít v dalším výpočtu (čti dál). Protože číslo řádku začíná na 1 a dělení 2 se implicitně převede na int, výsledkem je vytvoření sekvence 0 1 1 2 2 3 3 4 4 ... což má požadovaný výsledek:seskupením podle této vypočítané hodnoty, protože jsme také seřadili podle Num v čísle řádku jsme nyní dosáhli toho, že všechny množiny po prvním se skládají z Num =2 z "předchozího" řádku a Num =1 z "následujícího" řádku.

4. Dalším obtížným úkolem je vymyslet způsob, jak odstranit řádky, které nás nezajímají, a nějak sbalit čas začátku bloku do stejného řádku jako čas konce bloku. Chceme, aby každá samostatná sada Běh nebo Chůze dostala své vlastní číslo, abychom se podle ní mohli seskupit. DENSE_RANK() je přirozené řešení, ale problém je v tom, že věnuje pozornost každé hodnotě v ORDER BY klauzule--nemáme k dispozici syntaxi DENSE_RANK() OVER (PREORDER BY Time ORDER BY Name) takže Čas nezpůsobí RANK výpočet změnit kromě každé změny v Jméno . Po chvíli přemýšlení jsem si uvědomil, že bych mohl trochu vyčíst z logiky řešení seskupených ostrovů Itzika Ben-Gana, a zjistil jsem, že pořadí řádků seřazených podle Času , odečteno od pořadí řádků rozdělených podle Název a seřazené podle Času , by poskytla hodnotu, která by byla stejná pro každý řádek ve stejné skupině, ale odlišná od ostatních skupin. Obecná technika seskupených ostrovů spočívá ve vytvoření dvou vypočtených hodnot, které obě stoupají v lockstepu s řádky, jako je 4 5 6 a 1 2 3 , která po odečtení dá stejnou hodnotu (v tomto příkladu 3 3 3 jako výsledek 4 - 1 , 5–2 a 6–3 ). Poznámka:Původně jsem začínal s ROW_NUMBER() pro můj N výpočet, ale nefungovalo to. Správná odpověď byla DENSE_RANK() i když s lítostí musím říci, že si nepamatuji, proč jsem to tehdy uzavřel, a musel bych se do toho znovu ponořit, abych na to přišel. Ale stejně, to je to, co T-N vypočítává:číslo, které lze seskupit a izolovat každý „ostrov“ jednoho stavu (buď běh nebo chůze).

5. Ale to nebyl konec, protože tam jsou nějaké vrásky. Za prvé, „další“ řádek v každé skupině obsahuje nesprávné hodnoty pro Název , N a T . Obejdeme to tak, že z každé skupiny vybereme hodnotu z Num =2 řádek, když existuje (ale pokud ne, pak použijeme zbývající hodnotu). Získáte tak výrazy jako CASE WHEN NUM =2 THEN x END :to správně odstraní nesprávné hodnoty "dalšího" řádku.

6. Po nějakém experimentování jsem si uvědomil, že nestačí seskupit podle T - N sám o sobě, protože jak skupiny Walking, tak skupiny Running mohou mít stejnou vypočítanou hodnotu (v případě mých ukázkových dat poskytnutých do 17 existují dvě T - N hodnoty 6). Ale jednoduše seskupení podle Název také řeší tento problém. Žádná skupina „Běh“ nebo „Chůze“ nebude mít stejný počet mezilehlých hodnot z opačného typu. To znamená, že protože první skupina začíná „Běh“ a před další skupinou „Běh“ jsou dva řádky „Chůze“, bude hodnota pro N o 2 menší než hodnota pro T v této další skupině „Běh“. Právě jsem si uvědomil, že jedním ze způsobů, jak o tom přemýšlet, je T - N výpočet počítá počet řádků před aktuálním řádkem, které NEPATŘÍ ke stejné hodnotě "Běh" nebo "Chůze". Některé úvahy ukážou, že je to pravda:pokud přejdeme ke třetí skupině „Běh“, je to pouze třetí skupina, protože je odděluje skupina „Kráčí“, takže do ní přichází jiný počet zasahujících řad. před ním a vzhledem k tomu, že začíná na vyšší pozici, je dostatečně vysoká, takže hodnoty nelze duplikovat.

7. Konečně, protože naše poslední skupina se skládá pouze z jednoho řádku (není žádný čas ukončení a musíme zobrazit NULL místo toho) jsem musel zahrnout výpočet, který by mohl být použit k určení, zda máme konečný čas nebo ne. Toho se dosáhne pomocí Min(Num) výraz a nakonec zjištění, že když Min(Num) bylo 2 (což znamená, že jsme neměli "další" řádek), zobrazí se NULL místo Max(ToTime) hodnotu.

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

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

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

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