Hur kan jag upptäcka och binda ändringar mellan radvärden i en SQL-tabell?

Hitta "ToTime" med aggregat istället för en Join

Jag skulle vilja dela en riktigt vild fråga som bara tar 1 skanning av tabellen med 1 logisk läsning. Som jämförelse tar det bästa andra svaret på sidan, Simon Kingstons fråga, två skanningar.

På en mycket stor uppsättning data (17 408 inmatningsrader, vilket ger 8 193 resultatrader) tar det CPU 574 och tid 2645, medan Simon Kingstons fråga tar CPU 63 820 och tid 37 108.

Det är möjligt att med index skulle de andra frågorna på sidan kunna prestera många gånger bättre, men det är intressant för mig att uppnå 111x CPU-förbättring och 14x hastighetsförbättring bara genom att skriva om frågan.

(Observera:jag menar ingen som helst respektlöshet mot Simon Kingston eller någon annan; jag är helt enkelt exalterad över att min idé för den här frågan går så bra. Hans fråga är bättre än min eftersom dess prestanda är gott och det faktiskt är förståeligt och underhållbart , till skillnad från min.)

Här är den omöjliga frågan. Det är svårt att förstå. Det var svårt att skriva. Men det är häftigt. :)

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

Obs:Detta kräver SQL 2008 eller senare. För att få det att fungera i SQL 2005, ändra VALUES-satsen till SELECT 1 UNION ALL SELECT 2 .

Uppdaterad fråga

Efter att ha funderat lite på detta insåg jag att jag utförde två separata logiska uppgifter samtidigt, och detta gjorde frågan onödigt komplicerad:1) beskär mellanrader som inte har någon betydelse för den slutliga lösningen (rader som inte börjar en ny uppgift) och 2) dra "ToTime"-värdet från nästa rad. Genom att utföra #1 före #2, frågan är enklare och fungerar med ungefär hälften av CPU!

Så här är den förenklade frågan som först trimmar ut raderna vi inte bryr oss om, sedan får ToTime-värdet med hjälp av aggregat snarare än en JOIN. Ja, den har tre fönsterfunktioner istället för två, men i slutändan på grund av de färre raderna (efter beskärning av de vi inte bryr oss om) har den mindre arbete att göra:

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;

Den här uppdaterade frågan har alla samma problem som jag presenterade i min förklaring, men de är lättare att lösa eftersom jag inte har att göra med de extra onödiga raderna. Jag ser också att Row_Number() / 2 värdet 0 var jag tvungen att utesluta, och jag är inte säker på varför jag inte exkluderade det från den tidigare frågan, men i alla fall fungerar det perfekt och är otroligt snabbt!

Outre Apply städar upp saker och ting

Sist, här är en version som är i princip identisk med Simon Kingstons fråga som jag tycker är en lättare att förstå syntax.

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;

Här är installationsskriptet om du vill jämföra prestanda på en större datamängd:

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

Förklaring

Här är grundidén bakom min fråga.

1. Tiderna som representerar en växling måste visas i två intilliggande rader, en för att avsluta föregående aktivitet och en för att påbörja nästa aktivitet. Den naturliga lösningen på detta är en sammanfogning så att en utgångsrad kan dra från sin egen rad (för starttiden) och nästa ändras rad (för sluttiden).

2. Men min fråga åstadkommer behovet av att få sluttider att visas i två olika rader genom att upprepa raden två gånger, med CROSS JOIN (VALUES (1), (2)) . Vi har nu alla våra rader duplicerade. Tanken är att istället för att använda en JOIN för att göra beräkningar över kolumner, kommer vi att använda någon form av aggregering för att komprimera varje önskat par av rader till en.

3. Nästa uppgift är att göra varje dubblettrad delad ordentligt så att en instans går med föregående par och en med nästa par. Detta görs med T-kolumnen, en ROW_NUMBER() sorterad efter Time , och sedan dividerat med 2 (även om jag ändrade det gör en DENSE_RANK() för symmetri eftersom det i det här fallet returnerar samma värde som ROW_NUMBER). För effektivitetens skull utförde jag divisionen i nästa steg så att radnumret kunde återanvändas i en annan beräkning (fortsätt läsa). Eftersom radnummer börjar på 1, och att dividera med 2 implicit omvandlas till int, har detta effekten av att producera sekvensen 0 1 1 2 2 3 3 4 4 ... som ger önskat resultat:genom att gruppera efter detta beräknade värde, eftersom vi också sorterade efter Num i radnumret har vi nu åstadkommit att alla uppsättningar efter den första består av ett Num =2 från den "före" raden och ett Num =1 från "nästa" raden.

4. Nästa svåra uppgift är att komma på ett sätt att eliminera raderna vi inte bryr oss om och på något sätt kollapsa starttiden för ett block till samma rad som sluttiden för ett block. Vad vi vill är ett sätt att få varje diskret uppsättning löpning eller promenader att ges ett eget nummer så att vi kan gruppera efter det. DENSE_RANK() är en naturlig lösning, men ett problem är att den uppmärksammar varje värde i ORDER BY klausul--vi har inte syntax att göra DENSE_RANK() OVER (PREORDER BY Time ORDER BY Name) så att Time orsakar inte RANK beräkning att ändra utom vid varje ändring i Name . Efter lite funderande insåg jag att jag kunde krypa lite från logiken bakom Itzik Ben-Gans lösning för grupperade öar, och jag kom på att rangordningen på raderna sorterade efter Time , subtraherad från rangordningen för raderna som är partitionerade med Name och sorterade efter Time , skulle ge ett värde som var detsamma för varje rad i samma grupp men skiljer sig från andra grupper. Tekniken för generiska grupperade öar är att skapa två beräknade värden som båda stiger i låssteg med raderna som 4 5 6 och 1 2 3 , att när subtraherad kommer att ge samma värde (i det här exemplet 3 3 3 som ett resultat av 4 - 1 , 5 - 2 och 6 - 3 ). Obs! Jag började först med ROW_NUMBER() för mitt N beräkning men det fungerade inte. Rätt svar var DENSE_RANK() även om jag är ledsen att säga att jag inte kommer ihåg varför jag drog slutsatsen då, och jag skulle behöva dyka in igen för att ta reda på det. Men hur som helst, det är vad T-N beräknar:ett tal som kan grupperas på för att isolera varje "ö" med en status (antingen löpning eller promenad).

5. Men detta var inte slutet eftersom det finns några rynkor. Först och främst innehåller "nästa" rad i varje grupp de felaktiga värdena för Name , N och T . Vi kommer runt detta genom att välja, från varje grupp, värdet från Num = 2 rad när den finns (men om den inte gör det använder vi det återstående värdet). Detta ger uttryck som CASE WHEN NUM = 2 THEN x END :detta kommer att rensa bort de felaktiga värdena på "nästa" rad.

6. Efter lite experimenterande insåg jag att det inte räckte att gruppera efter T - N av sig själv, eftersom både promenadgrupperna och löpargrupperna kan ha samma beräknade värde (i fallet med mina exempeldata upp till 17 finns det två T - N värden på 6). Men helt enkelt gruppera efter Name löser även detta problem. Ingen grupp av vare sig "Running" eller "Walking" kommer att ha samma antal mellanliggande värden från den motsatta typen. Det vill säga, eftersom den första gruppen börjar med "Running", och det finns två "Walking"-rader som intervenerar före nästa "Running"-grupp, så kommer värdet för N att vara 2 mindre än värdet för T i nästa "Running"-grupp. Jag insåg precis att ett sätt att tänka på detta är att T - N beräkning räknar antalet rader före den aktuella raden som INTE tillhör samma värde "Running" eller "Walking". Vissa tankar kommer att visa att detta är sant:om vi går vidare till den tredje "Running"-gruppen, är det bara den tredje gruppen på grund av att en "Walking"-grupp separerar dem, så den har ett annat antal mellanliggande rader som kommer in före den, och på grund av att den börjar på en högre position, är den tillräckligt hög så att värdena inte kan dupliceras.

7. Slutligen, eftersom vår sista grupp bara består av en rad (det finns ingen sluttid och vi måste visa en NULL istället) fick jag slänga in en kalkyl som kunde användas för att avgöra om vi hade en sluttid eller inte. Detta görs med Min(Num) uttryck och sedan slutligen upptäcka att när Min(Num) var 2 (vilket betyder att vi inte hade en "nästa" rad) visar sedan en NULL istället för Max(ToTime) värde.

Jag hoppas att denna förklaring är till någon nytta för människor. Jag vet inte om min "radmultiplikeringsteknik" kommer att vara allmänt användbar och tillämpbar på de flesta SQL-frågeskrivare i produktionsmiljöer på grund av svårigheten att förstå den och och svårigheten att underhålla den med största säkerhet kommer att ge nästa person som besöker kod (reaktionen är förmodligen "Vad i hela friden gör den!?!" följt av ett snabbt "Dags att skriva om!").

Om du har kommit så långt så tackar jag dig för din tid och för att du ägnade mig åt min lilla utflykt till otroligt-roligt-sql-pussel-land.

Se det själv

A.k.a. simulerar en "FÖRORDNING AV":

En sista notering. För att se hur T - N gör jobbet – och noterar att användningen av den här delen av min metod kanske inte är allmänt tillämplig på SQL-gemenskapen – kör följande fråga mot de första 17 raderna av exempeldata:

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

Detta ger:

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

Den viktiga delen är att varje grupp av "Walking" eller "Running" har samma värde för T - N som är skild från alla andra grupper med samma namn.

Prestanda

Jag vill inte understryka poängen med att min fråga är snabbare än andras. Men med tanke på hur slående skillnaden är (när det inte finns några index) ville jag visa siffrorna i ett tabellformat. Detta är en bra teknik när hög prestanda av denna typ av rad-till-rad-korrelation krävs.

Innan varje fråga kördes använde jag DBCC FREEPROCCACHE; DBCC DROPCLEANBUFFERS; . Jag satte MAXDOP till 1 för varje fråga för att ta bort de tidskollapsande effekterna av parallellism. Jag valde varje resultatuppsättning i variabler istället för att returnera dem till klienten för att bara mäta prestanda och inte klientdataöverföring. Alla frågor fick samma ORDER BY-klausuler. Alla tester använde 17 408 inmatningsrader vilket gav 8 193 resultatrader.

Inga resultat visas av följande personer/skäl:

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

Utan index:

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

Med index 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

Med index 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

Så moralen i berättelsen är:

Lämpliga index är viktigare än frågeguide

Med lämpligt index vinner Simon Kingstons version totalt sett, särskilt när den inkluderar frågekomplexitet/underhållbarhet.

Följ denna lektion väl! 38k läsningar är egentligen inte så många, och Simon Kingstons version körde på halva tiden som min. Hastighetsökningen för min fråga berodde helt och hållet på att det inte fanns något index på bordet, och den åtföljande katastrofala kostnaden detta gav för alla frågor som behövde en join (vilket min inte gjorde):en fullständig tabellskanning av Hash Match som dödade dess prestanda. Med ett index kunde hans fråga göra en kapslad loop med en klustrad indexsökning (a.k.a. en bokmärkessökning) som gjorde saker på riktigt snabbt.

Det är intressant att det inte räckte med ett klustrat index på bara Time. Även om tiderna var unika, vilket betyder att endast ett namn förekom per gång, behövde det fortfarande Namn vara en del av indexet för att kunna använda det korrekt.

Att lägga till det klustrade indexet i tabellen när det var fullt av data tog under 1 sekund! Försumma inte dina index.