Sådan finder du "ToTime" efter aggregater i stedet for en joinforbindelse
Jeg vil gerne dele en rigtig vild forespørgsel, der kun tager 1 scanning af tabellen med 1 logisk læsning. Til sammenligning tager det bedste andet svar på siden, Simon Kingstons forespørgsel, 2 scanninger.
På et meget stort sæt data (17.408 inputrækker, der giver 8.193 resultatrækker) tager det CPU 574 og tid 2645, mens Simon Kingstons forespørgsel tager CPU 63.820 og tid 37.108.
Det er muligt, at de andre forespørgsler på siden med indekser kunne klare sig mange gange bedre, men det er interessant for mig at opnå 111x CPU-forbedring og 14x hastighedsforbedring blot ved at omskrive forespørgslen.
(Bemærk venligst:Jeg mener overhovedet ingen respektløshed over for Simon Kingston eller nogen anden; jeg er simpelthen begejstret for, at min idé til denne forespørgsel forløber så godt. Hans forespørgsel er bedre end min, da dens ydeevne er rigelig, og den faktisk er forståelig og vedligeholdelig , i modsætning til min.)
Her er den umulige forespørgsel. Det er svært at forstå. Det var svært at skrive. Men det er fantastisk. :)
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
Bemærk:Dette kræver SQL 2008 eller nyere. For at få det til at fungere i SQL 2005 skal du ændre VALUES-sætningen til SELECT 1 UNION ALL SELECT 2
.
Opdateret forespørgsel
Efter at have tænkt lidt over dette, indså jeg, at jeg var i gang med to separate logiske opgaver på samme tid, og det gjorde forespørgslen unødvendigt kompliceret:1) beskær mellemliggende rækker, der ikke har nogen betydning for den endelige løsning (rækker, der ikke begynder). en ny opgave) og 2) træk "ToTime"-værdien fra næste række. Ved at udføre #1 før #2, forespørgslen er enklere og fungerer med cirka halvdelen af CPU'en!
Så her er den forenklede forespørgsel, der først trimmer de rækker ud, som vi er ligeglade med, derefter får ToTime-værdien ved hjælp af aggregater i stedet for en JOIN. Ja, den har 3 vinduesfunktioner i stedet for 2, men i sidste ende på grund af de færre rækker (efter beskæring af dem, vi er ligeglade med) har den mindre arbejde at gøre:
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;
Denne opdaterede forespørgsel har alle de samme problemer, som jeg præsenterede i min forklaring, men de er nemmere at løse, fordi jeg ikke har at gøre med de ekstra unødvendige rækker. Jeg kan også se, at Row_Number() / 2
værdi på 0 var jeg nødt til at ekskludere, og jeg er ikke sikker på, hvorfor jeg ikke ekskluderede den fra den tidligere forespørgsel, men under alle omstændigheder fungerer dette perfekt og er utroligt hurtigt!
Over brug ordner tingene
Til sidst er her en version, der grundlæggende er identisk med Simon Kingstons forespørgsel, som jeg synes er en lettere at forstå syntaks.
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;
Her er opsætningsscriptet, hvis du ønsker at sammenligne ydeevne på et større datasæt:
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
Forklaring
Her er den grundlæggende idé bag min forespørgsel.
-
Tiderne, der repræsenterer et skifte, skal vises i to tilstødende rækker, en for at afslutte den foregående aktivitet og en for at begynde den næste aktivitet. Den naturlige løsning på dette er en joinforbindelse, så en outputrække kan trække fra sin egen række (til starttidspunktet) og næste ændrede række (til sluttidspunktet).
-
Men min forespørgsel opfylder behovet for at få sluttider til at vises i to forskellige rækker ved at gentage rækken to gange med
CROSS JOIN (VALUES (1), (2))
. Vi har nu alle vores rækker duplikeret. Ideen er, at i stedet for at bruge en JOIN til at lave beregninger på tværs af kolonner, bruger vi en form for aggregering til at kollapse hvert ønsket par af rækker til én. -
Den næste opgave er at få hver dubletrække til at opdele korrekt, så en instans går med det foregående par og en med det næste par. Dette opnås med T-kolonnen, en
ROW_NUMBER()
sorteret efterTime
, og derefter divideret med 2 (selvom jeg ændrede det, gør en DENSE_RANK() for symmetri, da det i dette tilfælde returnerer den samme værdi som ROW_NUMBER). For effektivitetens skyld udførte jeg opdelingen i næste trin, så rækkenummeret kunne genbruges i en anden beregning (fortsæt med at læse). Da rækkenummer starter ved 1, og at dividere med 2 implicit konverterer til int, har dette den effekt at producere sekvensen0 1 1 2 2 3 3 4 4 ...
som har det ønskede resultat:ved at gruppere efter denne beregnede værdi, da vi også sorterede efterNum
i rækkenummeret har vi nu opnået, at alle sæt efter det første består af et Num =2 fra den "forrige" række og et Num =1 fra den "næste" række. -
Den næste svære opgave er at finde ud af en måde at eliminere de rækker, vi er ligeglade med, og på en eller anden måde kollapse starttidspunktet for en blok til den samme række som sluttidspunktet for en blok. Det, vi ønsker, er en måde at få hvert enkelt sæt løb eller gå til at få sit eget nummer, så vi kan gruppere efter det.
DENSE_RANK()
er en naturlig løsning, men et problem er, at den er opmærksom på hver værdi iORDER BY
klausul--vi har ikke syntaks at gøreDENSE_RANK() OVER (PREORDER BY Time ORDER BY Name)
såTime
forårsager ikkeRANK
beregning at ændre undtagen ved hver ændring iName
. Efter nogle overvejelser indså jeg, at jeg kunne krybe lidt fra logikken bag Itzik Ben-Gans grupperede ø-løsning, og jeg fandt ud af, at rækkernes rækkefølge sorteret efterTime
, trukket fra rækken af rækkerne opdelt medName
og sorteret efterTime
, ville give en værdi, der var den samme for hver række i den samme gruppe, men forskellig fra andre grupper. Den generiske gruppede ø-teknik er at skabe to beregnede værdier, der begge stiger i låsetrin med rækkerne såsom4 5 6
og1 2 3
, at når det trækkes fra, vil det give den samme værdi (i dette eksempel tilfælde3 3 3
som resultatet af4 - 1
,5 - 2
og6 - 3
). Bemærk:Jeg startede oprindeligt medROW_NUMBER()
for mitN
udregning, men det virkede ikke. Det rigtige svar varDENSE_RANK()
Selvom jeg er ked af at sige, at jeg ikke kan huske, hvorfor jeg konkluderede dette på det tidspunkt, og jeg ville være nødt til at dykke ind igen for at finde ud af det. Men alligevel, det er hvadT-N
beregner:et tal, der kan grupperes på for at isolere hver "ø" med én status (enten Løb eller Gå). -
Men dette var ikke slutningen, fordi der er nogle rynker. Først og fremmest indeholder den "næste" række i hver gruppe de forkerte værdier for
Name
,N
ogT
. Vi kommer uden om dette ved at vælge værdien fraNum = 2
fra hver gruppe række, når den findes (men hvis den ikke gør det, så bruger vi den resterende værdi). Dette giver udtryk somCASE WHEN NUM = 2 THEN x END
:dette vil korrekt luge de forkerte "næste" rækkeværdier ud. -
Efter nogle eksperimenter indså jeg, at det ikke var nok at gruppere efter
T - N
af sig selv, fordi både Walking-grupperne og Løbegrupperne kan have den samme beregnede værdi (i tilfælde af mine eksempeldata, der er angivet op til 17, er der toT - N
værdier på 6). Men bare gruppering efterName
løser også dette problem. Ingen gruppe af hverken "Løber" eller "Gående" vil have det samme antal mellemliggende værdier fra den modsatte type. Det vil sige, at da den første gruppe starter med "Running", og der er to "Walking"-rækker, der griber ind før den næste "Running"-gruppe, så vil værdien for N være 2 mindre end værdien forT
i den næste "løbende" gruppe. Jeg har lige indset, at en måde at tænke på dette er, atT - N
beregning tæller antallet af rækker før den aktuelle række, der IKKE hører til den samme værdi "Running" eller "Walking". Nogle tanker vil vise, at dette er sandt:Hvis vi går videre til den tredje "Running"-gruppe, er det kun den tredje gruppe i kraft af at have en "Walking"-gruppe, der adskiller dem, så den har et andet antal mellemliggende rækker, der kommer ind før den, og fordi den starter i en højere position, er den høj nok til, at værdierne ikke kan duplikeres. -
Endelig, da vores sidste gruppe kun består af én række (der er ingen sluttidspunkt, og vi skal vise en
NULL
i stedet) måtte jeg smide et regnestykke ind, som kunne bruges til at afgøre, om vi havde et sluttidspunkt eller ej. Dette opnås medMin(Num)
udtryk og så endelig detektere, at når Min(Num) var 2 (hvilket betyder, at vi ikke havde en "næste" række), så vis enNULL
i stedet forMax(ToTime)
værdi.
Jeg håber, at denne forklaring er til nogen nytte for folk. Jeg ved ikke, om min "row-multiplying"-teknik generelt vil være nyttig og anvendelig til de fleste SQL-forespørgselsskrivere i produktionsmiljøer på grund af vanskelighederne med at forstå den og og vanskelighederne ved vedligeholdelse, den helt sikkert vil give den næste person, der besøger kode (reaktionen er sandsynligvis "Hvad i alverden laver den!?!" efterfulgt af et hurtigt "Tid til at omskrive!").
Hvis du er nået så langt, så takker jeg dig for din tid og for at forkæle mig med min lille udflugt til utroligt-sjovt-sql-puslespil-land.
Se det selv
A.k.a. simulerer en "FORUDORDNING AF":
En sidste bemærkning. For at se hvordan T - N
udfører jobbet - og bemærker, at brugen af denne del af min metode muligvis ikke er generelt anvendelig for SQL-fællesskabet - kør følgende forespørgsel mod de første 17 rækker af eksempeldataene:
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];
Dette giver:
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 vigtige del er, at hver gruppe af "Gå" eller "Løb" har den samme værdi for T - N
der er forskellig fra enhver anden gruppe med samme navn.
Ydeevne
Jeg ønsker ikke at uddybe pointen med, at min forespørgsel er hurtigere end andres. Men i betragtning af hvor slående forskellen er (når der ikke er nogen indeks), ville jeg vise tallene i et tabelformat. Dette er en god teknik, når høj ydeevne af denne slags række-til-række-korrelation er nødvendig.
Før hver forespørgsel kørte, brugte jeg DBCC FREEPROCCACHE; DBCC DROPCLEANBUFFERS;
. Jeg satte MAXDOP til 1 for hver forespørgsel for at fjerne de tidskollapsende virkninger af parallelisme. Jeg valgte hvert resultatsæt i variabler i stedet for at returnere dem til klienten for kun at måle ydeevne og ikke klientdatatransmission. Alle forespørgsler fik de samme ORDER BY-klausuler. Alle test brugte 17.408 inputrækker, hvilket gav 8.193 resultatrækker.
Der vises ingen resultater af følgende personer/årsager:
RichardTheKiwi *Could not test--query needs updating*
ypercube *No SQL 2012 environment yet :)*
Tim S *Did not complete tests within 5 minutes*
Uden indeks:
CPU Duration Reads Writes
----------- ----------- ----------- -----------
ErikE 344 344 99 0
Simon Kingston 68672 69582 549203 49
Med indeks 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 indeks 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 historien er:
Relevante indekser er vigtigere end forespørgselstrolldom
Med det passende indeks vinder Simon Kingstons version generelt, især når den inkluderer forespørgselskompleksitet/vedligeholdelse.
Pas godt på denne lektion! 38k læsninger er egentlig ikke så mange, og Simon Kingstons version kørte på halvdelen af tiden som min. Hastighedsforøgelsen af min forespørgsel skyldtes udelukkende, at der ikke var noget indeks på bordet, og de samtidige katastrofale omkostninger, som dette gav enhver forespørgsel, der havde brug for en join (hvilket min ikke gjorde):en fuld tabelscanning Hash Match, der dræbte dens ydeevne. Med et indeks var hans forespørgsel i stand til at lave en indlejret løkke med en klynget indekssøgning (a.k.a. et bogmærkeopslag), som gjorde tingene virkelig hurtigt.
Det er interessant, at et klynget indeks på Time alene ikke var nok. Selvom Times var unikke, hvilket betyder, at der kun opstod ét navn pr. gang, skulle det stadigvæk have Navn til at være en del af indekset for at kunne bruge det korrekt.
Tilføjelse af det klyngede indeks til tabellen, når det var fyldt med data, tog under 1 sekund! Forsøm ikke dine indekser.