ToTime vinden door middel van aggregaten in plaats van een join
Ik wil graag een heel wilde vraag delen die slechts 1 scan van de tabel nodig heeft met 1 logische lezing. Ter vergelijking:voor het beste andere antwoord op de pagina, de vraag van Simon Kingston, zijn 2 scans nodig.
Op een zeer grote set gegevens (17.408 invoerrijen, met 8.193 resultaatrijen) kost het CPU 574 en tijd 2645, terwijl de query van Simon Kingston CPU 63.820 en tijd 37.108 kost.
Het is mogelijk dat met indexen de andere zoekopdrachten op de pagina vele malen beter zouden presteren, maar het is voor mij interessant om 111x CPU-verbetering en 14x snelheidsverbetering te bereiken door de zoekopdracht te herschrijven.
(Let op:ik bedoel helemaal geen gebrek aan respect voor Simon Kingston of iemand anders; ik ben gewoon enthousiast over mijn idee voor deze vraag die zo goed uitpakt. Zijn vraag is beter dan de mijne omdat de prestaties voldoende zijn en het eigenlijk begrijpelijk en onderhoudbaar is , in tegenstelling tot de mijne.)
Hier is de onmogelijke vraag. Het is moeilijk te begrijpen. Het was moeilijk om te schrijven. Maar het is geweldig. :)
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
Opmerking:hiervoor is SQL 2008 of hoger vereist. Om het te laten werken in SQL 2005, wijzigt u de VALUES-clausule in SELECT 1 UNION ALL SELECT 2 .
Bijgewerkte zoekopdracht
Nadat ik hier even over had nagedacht, realiseerde ik me dat ik twee afzonderlijke logische taken tegelijkertijd uitvoerde, en dit maakte de query onnodig ingewikkeld:1) snoei tussenliggende rijen weg die geen invloed hebben op de uiteindelijke oplossing (rijen die niet beginnen een nieuwe taak) en 2) haal de waarde "ToTime" uit de volgende rij. Door #1 vóór . uit te voeren #2, de zoekopdracht is eenvoudiger en werkt met ongeveer de helft van de CPU!
Dus hier is de vereenvoudigde zoekopdracht die eerst de rijen wegsnijdt waar we niet om geven, dan haalt de ToTime-waarde op met behulp van aggregaten in plaats van een JOIN. Ja, het heeft 3 vensterfuncties in plaats van 2, maar uiteindelijk vanwege de minder rijen (na het snoeien van die waar we niet om geven) heeft het minder werk te doen:
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;
Deze bijgewerkte query heeft dezelfde problemen als ik in mijn uitleg heb gepresenteerd, maar ze zijn gemakkelijker op te lossen omdat ik niet te maken heb met de extra onnodige rijen. Ik zie ook dat de Row_Number() / 2 waarde van 0 die ik moest uitsluiten, en ik weet niet zeker waarom ik het niet heb uitgesloten van de vorige zoekopdracht, maar dit werkt in ieder geval perfect en is verbazingwekkend snel!
Buitenste dingen opruimen
Ten slotte is hier een versie die in wezen identiek is aan de vraag van Simon Kingston, waarvan ik denk dat deze een gemakkelijker te begrijpen syntaxis is.
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;
Hier is het setup-script als je prestatievergelijking wilt doen op een grotere dataset:
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
Uitleg
Hier is het basisidee achter mijn vraag.
-
De tijden die een schakelaar vertegenwoordigen, moeten in twee aangrenzende rijen verschijnen, één om de vorige activiteit te beëindigen en één om de volgende activiteit te beginnen. De natuurlijke oplossing hiervoor is een join zodat een uitvoerrij uit zijn eigen rij kan trekken (voor de starttijd) en de volgende gewijzigde rij (voor de eindtijd).
-
Echter, mijn vraag volbrengt de noodzaak om eindtijden in twee verschillende rijen te laten verschijnen door de rij twee keer te herhalen, met
CROSS JOIN (VALUES (1), (2)). We hebben nu al onze rijen gedupliceerd. Het idee is dat in plaats van een JOIN te gebruiken om berekeningen over kolommen uit te voeren, we een of andere vorm van aggregatie zullen gebruiken om elk gewenst paar rijen in één samen te vouwen. -
De volgende taak is om elke dubbele rij correct te splitsen, zodat één exemplaar bij het vorige paar past en één exemplaar bij het volgende paar. Dit wordt bereikt met de T-kolom, een
ROW_NUMBER()besteld opTime, en vervolgens gedeeld door 2 (hoewel ik het heb gewijzigd, doe een DENSE_RANK() voor symmetrie, omdat het in dit geval dezelfde waarde retourneert als ROW_NUMBER). Voor de efficiëntie heb ik de deling in de volgende stap uitgevoerd, zodat het rijnummer opnieuw kon worden gebruikt in een andere berekening (lees verder). Aangezien rijnummer begint bij 1, en delen door 2 impliciet converteert naar int, heeft dit tot gevolg dat de reeks0 1 1 2 2 3 3 4 4 ...ontstaat wat het gewenste resultaat heeft:door te groeperen op deze berekende waarde, aangezien we ook bestelden opNumin het rijnummer hebben we nu bereikt dat alle sets na de eerste een Num =2 van de "vorige" rij en een Num =1 van de "volgende" rij bevatten. -
De volgende moeilijke taak is het bedenken van een manier om de rijen te elimineren waar we niet om geven en op de een of andere manier de starttijd van een blok in te klappen in dezelfde rij als de eindtijd van een blok. Wat we willen is een manier om elke afzonderlijke set van hardlopen of wandelen een eigen nummer te geven, zodat we er op kunnen groeperen.
DENSE_RANK()is een natuurlijke oplossing, maar een probleem is dat het aandacht besteedt aan elke waarde in deORDER BYclausule--we hebben geen syntaxis om te doenDENSE_RANK() OVER (PREORDER BY Time ORDER BY Name)zodat deTimeveroorzaakt niet deRANKberekening te wijzigen behalve bij elke wijziging inName. Na enig nadenken realiseerde ik me dat ik een beetje kon griezelen van de logica achter Itzik Ben-Gan's oplossing voor gegroepeerde eilanden, en ik kwam erachter dat de rangorde van de rijen geordend opTime, afgetrokken van de rangorde van de rijen gepartitioneerd doorNameen besteld opTime, zou een waarde opleveren die voor elke rij in dezelfde groep hetzelfde was, maar anders dan voor andere groepen. De generieke techniek van gegroepeerde eilanden is om twee berekende waarden te creëren die beide in lockstep stijgen met de rijen zoals4 5 6en1 2 3, dat wanneer afgetrokken dezelfde waarde oplevert (in dit voorbeeld3 3 3als resultaat van4 - 1,5 - 2, en6 - 3). Opmerking:ik begon in eerste instantie metROW_NUMBER()voor mijnNrekenen, maar het werkte niet. Het juiste antwoord wasDENSE_RANK()hoewel het spijt me te moeten zeggen dat ik niet meer weet waarom ik dit destijds concludeerde, en ik zou er opnieuw in moeten duiken om erachter te komen. Maar goed, dat is watT-Nberekent:een getal dat kan worden gegroepeerd om elk "eiland" van één status te isoleren (rennen of wandelen). -
Maar dit was niet het einde want er zijn wat rimpels. Allereerst bevat de "volgende" rij in elke groep de onjuiste waarden voor
Name,N, enT. We omzeilen dit door uit elke groep de waarde te selecteren uit hetNum = 2rij wanneer deze bestaat (maar als deze niet bestaat, gebruiken we de resterende waarde). Dit levert de uitdrukkingen op alsCASE WHEN NUM = 2 THEN x END:dit zal de onjuiste "volgende" rijwaarden verwijderen. -
Na wat experimenteren realiseerde ik me dat het niet genoeg was om te groeperen op
T - Nop zichzelf, omdat zowel de groepen Lopen als de groepen Hardlopen dezelfde berekende waarde kunnen hebben (in het geval van mijn voorbeeldgegevens tot 17, zijn er tweeT - Nwaarden van 6). Maar gewoon groeperen opNamelost ook dit probleem op. Geen enkele groep van "Hardlopen" of "Wandelen" heeft hetzelfde aantal tussenliggende waarden van het tegenovergestelde type. Dat wil zeggen, aangezien de eerste groep begint met "Rennen", en er twee "Walking"-rijen tussenkomen voor de volgende "Running"-groep, zal de waarde voor N 2 minder zijn dan de waarde voorTin die volgende "Running" groep. Ik realiseerde me net dat een manier om hierover na te denken is dat deT - Nberekening telt het aantal rijen voor de huidige rij die NIET bij dezelfde waarde "Hardlopen" of "Wandelen" horen. Sommige gedachten zullen aantonen dat dit waar is:als we verder gaan met de derde groep "Hardlopen", is het pas de derde groep omdat er een "Loop"-groep is die hen scheidt, dus er komt een ander aantal tussenliggende rijen binnen ervoor, en omdat het op een hogere positie begint, is het hoog genoeg zodat de waarden niet kunnen worden gedupliceerd. -
Ten slotte, aangezien onze laatste groep uit slechts één rij bestaat (er is geen eindtijd en we moeten een
NULLweergeven in plaats daarvan) moest ik een berekening toevoegen die kon worden gebruikt om te bepalen of we een eindtijd hadden of niet. Dit wordt bereikt met deMin(Num)expressie en dan uiteindelijk detecteren dat wanneer de Min (Num) 2 was (wat betekent dat we geen "volgende" rij hadden), dan eenNULLweergeven in plaats van deMax(ToTime)waarde.
Ik hoop dat deze uitleg van enig nut is voor mensen. Ik weet niet of mijn "rij-vermenigvuldiging"-techniek over het algemeen nuttig en toepasbaar zal zijn op de meeste SQL-queryschrijvers in productieomgevingen vanwege de moeilijkheid om het te begrijpen en en de moeilijkheid van onderhoud die het zeker zal opleveren voor de volgende persoon die de site bezoekt. code (de reactie is waarschijnlijk "Wat is het in vredesnaam aan het doen!?!" gevolgd door een snelle "Tijd om te herschrijven!").
Als je zo ver bent gekomen, dan wil ik je bedanken voor je tijd en dat je me hebt overgegeven aan mijn kleine excursie naar ongelooflijk-leuk-sql-puzzelland.
Zie het zelf
ook bekend als simuleren van een "PREORDER BY":
Een laatste opmerking. Om te zien hoe T - N doet het werk - en merk op dat het gebruik van dit deel van mijn methode mogelijk niet algemeen van toepassing is op de SQL-gemeenschap - voer de volgende query uit op de eerste 17 rijen van de voorbeeldgegevens:
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];
Dit levert:
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
Het belangrijkste is dat elke groep "Lopen" of "Rennen" dezelfde waarde heeft voor T - N die verschilt van elke andere groep met dezelfde naam.
Prestaties
Ik wil niet uitweiden over het punt dat mijn vraag sneller is dan die van andere mensen. Echter, gezien hoe opvallend het verschil is (wanneer er geen indexen zijn), wilde ik de getallen in een tabelformaat weergeven. Dit is een goede techniek wanneer hoge prestaties van dit soort rij-naar-rij-correlatie nodig zijn.
Voordat elke query werd uitgevoerd, gebruikte ik DBCC FREEPROCCACHE; DBCC DROPCLEANBUFFERS; . Ik heb MAXDOP voor elke query op 1 gezet om de tijdvernietigende effecten van parallellisme te verwijderen. Ik selecteerde elke resultaatset in variabelen in plaats van ze terug te sturen naar de klant om alleen de prestaties te meten en niet de overdracht van klantgegevens. Alle zoekopdrachten kregen dezelfde ORDER BY-clausules. Alle tests gebruikten 17.408 invoerrijen die 8.193 resultaatrijen opleverden.
Er worden geen resultaten weergegeven voor de volgende personen/redenen:
RichardTheKiwi *Could not test--query needs updating*
ypercube *No SQL 2012 environment yet :)*
Tim S *Did not complete tests within 5 minutes*
Zonder index:
CPU Duration Reads Writes
----------- ----------- ----------- -----------
ErikE 344 344 99 0
Simon Kingston 68672 69582 549203 49
Met 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
Met 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
Dus de moraal van het verhaal is:
Adequate indexen zijn belangrijker dan tovenarij opvragen
Met de juiste index wint de versie van Simon Kingston over het algemeen, vooral als de complexiteit/onderhoudbaarheid van de query wordt meegerekend.
Luister goed naar deze les! 38k leest is niet echt veel, en Simon Kingston's versie liep in de helft van de tijd als de mijne. De snelheidsverhoging van mijn zoekopdracht was volledig te wijten aan het ontbreken van een index op de tafel, en de daarmee gepaard gaande catastrofale kosten die dit gaf aan elke zoekopdracht die een join nodig had (wat de mijne niet deed):een volledige tabelscan van Hash Match die zijn prestaties doodt. Met een index was zijn zoekopdracht in staat om een geneste lus uit te voeren met een geclusterde indexzoekopdracht (ook wel een bladwijzerzoekopdracht genoemd) die dingen echt maakte snel.
Interessant is dat een geclusterde index op Time alleen niet voldoende was. Hoewel Times uniek was, wat inhoudt dat er slechts één naam per keer voorkwam, moest Naam toch deel uitmaken van de index om deze correct te kunnen gebruiken.
Het toevoegen van de geclusterde index aan de tabel als deze vol was met gegevens duurde minder dan 1 seconde! Verwaarloos uw indexen niet.