Trovare "ToTime" in base a aggregati anziché a join
Vorrei condividere una query davvero selvaggia che richiede solo 1 scansione della tabella con 1 lettura logica. In confronto, l'altra migliore risposta sulla pagina, la domanda di Simon Kingston, richiede 2 scansioni.
Su un set di dati molto ampio (17.408 righe di input, producendo 8.193 righe di risultati) ci vogliono CPU 574 e tempo 2645, mentre la query di Simon Kingston richiede CPU 63.820 e tempo 37.108.
È possibile che con gli indici le altre query sulla pagina possano funzionare molto meglio, ma è interessante per me ottenere un miglioramento della CPU 111x e un miglioramento della velocità 14x semplicemente riscrivendo la query.
(Nota:non intendo mancare di rispetto a Simon Kingston o a chiunque altro; sono semplicemente entusiasta della mia idea per questa query che è andata così bene. La sua query è migliore della mia poiché le sue prestazioni sono abbondanti ed è effettivamente comprensibile e gestibile , a differenza del mio.)
Ecco la domanda impossibile. È difficile da capire. Era difficile scrivere. Ma è fantastico. :)
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
Nota:questo richiede SQL 2008 o versioni successive. Per farlo funzionare in SQL 2005, cambia la clausola VALUES in SELECT 1 UNION ALL SELECT 2 .
Query aggiornata
Dopo averci pensato un po', mi sono reso conto che stavo eseguendo due compiti logici separati contemporaneamente, e questo ha reso la query inutilmente complicata:1) eliminare le righe intermedie che non hanno attinenza con la soluzione finale (righe che non iniziano una nuova attività) e 2) estrarre il valore "ToTime" dalla riga successiva. Eseguendo #1 prima #2, la query è più semplice e funziona con circa metà della CPU!
Quindi ecco la query semplificata che prima taglia le righe che non ci interessano, poi ottiene il valore ToTime utilizzando aggregati anziché JOIN. Sì, ha 3 funzioni di windowing invece di 2, ma alla fine a causa del minor numero di righe (dopo aver eliminato quelle che non ci interessano) ha meno lavoro da fare:
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;
Questa query aggiornata presenta tutti gli stessi problemi che ho presentato nella mia spiegazione, tuttavia sono più facili da risolvere perché non ho a che fare con le righe extra non necessarie. Vedo anche che il Row_Number() / 2 valore di 0 l'ho dovuto escludere e non sono sicuro del motivo per cui non l'ho escluso dalla query precedente, ma in ogni caso funziona perfettamente ed è incredibilmente veloce!
L'applicazione esterna riordina le cose
Infine, ecco una versione sostanzialmente identica alla query di Simon Kingston che penso sia una sintassi più facile da capire.
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;
Ecco lo script di installazione se desideri confrontare le prestazioni su un set di dati più ampio:
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
Spiegazione
Ecco l'idea di base alla base della mia domanda.
-
Gli orari che rappresentano un cambio devono apparire in due righe adiacenti, una per terminare l'attività precedente e una per iniziare l'attività successiva. La soluzione naturale a questo è un join in modo che una riga di output possa estrarre dalla propria riga (per l'ora di inizio) e il successivo modificato riga (per l'ora di fine).
-
Tuttavia, la mia query soddisfa la necessità di far apparire gli orari di fine in due righe diverse ripetendo la riga due volte, con
CROSS JOIN (VALUES (1), (2)). Ora abbiamo tutte le nostre righe duplicate. L'idea è che invece di utilizzare un JOIN per eseguire calcoli su colonne, utilizzeremo una qualche forma di aggregazione per comprimere ciascuna coppia di righe desiderata in una. -
L'attività successiva consiste nel dividere correttamente ogni riga duplicata in modo che un'istanza vada con la coppia precedente e una con la coppia successiva. Questo si ottiene con la colonna T, un
ROW_NUMBER()ordinato perTime, e quindi diviso per 2 (anche se l'ho modificato, esegue un DENSE_RANK() per simmetria poiché in questo caso restituisce lo stesso valore di ROW_NUMBER). Per efficienza ho eseguito la divisione nel passaggio successivo in modo che il numero di riga potesse essere riutilizzato in un altro calcolo (continua a leggere). Poiché il numero di riga inizia da 1 e la divisione per 2 si converte implicitamente in int, questo ha l'effetto di produrre la sequenza0 1 1 2 2 3 3 4 4 ...che ha il risultato desiderato:raggruppando per questo valore calcolato, poiché abbiamo ordinato anche perNumnel numero di riga, abbiamo ora ottenuto che tutti gli insiemi dopo il primo siano composti da un Num =2 dalla riga "precedente" e un Num =1 dalla riga "successiva". -
Il prossimo compito difficile è trovare un modo per eliminare le righe che non ci interessano e in qualche modo comprimere l'ora di inizio di un blocco nella stessa riga dell'ora di fine di un blocco. Quello che vogliamo è un modo per far sì che a ciascun insieme discreto di Corsa o Camminata venga assegnato il proprio numero in modo da poterlo raggruppare in base a esso.
DENSE_RANK()è una soluzione naturale, ma un problema è che presta attenzione a ogni valore nelORDER BYclausola--non abbiamo la sintassi per fareDENSE_RANK() OVER (PREORDER BY Time ORDER BY Name)in modo che ilTimenon causa ilRANKcalcolo da modificare tranne per ogni modifica inName. Dopo averci pensato un po', mi sono reso conto che potevo sfruttare un po' la logica alla base della soluzione delle isole raggruppate di Itzik Ben-Gan e ho capito che il rango delle righe ordinate perTime, sottratto dal rango delle righe partizionate perNamee ordinato perTime, produrrebbe un valore uguale per ogni riga nello stesso gruppo ma diverso dagli altri gruppi. La tecnica generica delle isole raggruppate consiste nel creare due valori calcolati che salgono entrambi di pari passo con le righe come4 5 6e1 2 3, che una volta sottratto restituirà lo stesso valore (in questo caso di esempio3 3 3come risultato di4 - 1,5 - 2e6 - 3). Nota:inizialmente ho iniziato conROW_NUMBER()per il mioNcalcolo ma non funzionava. La risposta corretta eraDENSE_RANK()anche se mi dispiace dire che non ricordo perché l'ho concluso in quel momento, e dovrei immergermi di nuovo per capirlo. Ma comunque, questo è ciò cheT-Ncalcola:un numero che può essere raggruppato per isolare ogni "isola" di uno stato (in esecuzione o in marcia). -
Ma questa non era la fine perché ci sono alcune rughe. Prima di tutto, la riga "successivo" in ogni gruppo contiene i valori errati per
Name,NeT. Lo aggiriamo selezionando, da ciascun gruppo, il valore daNum = 2riga quando esiste (ma in caso contrario, utilizziamo il valore rimanente). Questo produce espressioni comeCASE WHEN NUM = 2 THEN x END:questo eliminerà correttamente i valori di riga "successivi" errati. -
Dopo qualche sperimentazione, mi sono reso conto che non bastava raggruppare per
T - Nda solo, perché sia i gruppi Camminata che i gruppi Corsa possono avere lo stesso valore calcolato (nel caso dei miei dati di esempio forniti fino a 17, ci sono dueT - Nvalori di 6). Ma semplicemente raggruppando perNamerisolve anche questo problema. Nessun gruppo di "Running" o "Walking" avrà lo stesso numero di valori intermedi del tipo opposto. Cioè, poiché il primo gruppo inizia con "Running" e ci sono due righe "Walking" che intervengono prima del successivo gruppo "Running", il valore di N sarà 2 inferiore al valore diTnel prossimo gruppo "Running". Mi sono appena reso conto che un modo per pensarci è che ilT - Ncalcolo conta il numero di righe prima della riga corrente che NON appartengono allo stesso valore "Running" o "Walking". Qualche pensiero mostrerà che questo è vero:se passiamo al terzo gruppo "Running", è solo il terzo gruppo in virtù di avere un gruppo "Walking" che li separa, quindi ha un numero diverso di righe intermedie in arrivo prima di esso, e poiché parte da una posizione più alta, è abbastanza alto da non poter duplicare i valori. -
Infine, poiché il nostro gruppo finale è costituito da una sola riga (non esiste un'ora di fine e dobbiamo visualizzare un
NULLinvece) ho dovuto inserire un calcolo che potesse essere utilizzato per determinare se avevamo o meno un'ora di fine. Questo si ottiene con ilMin(Num)espressione e quindi alla fine rilevando che quando Min(Num) era 2 (il che significa che non avevamo una riga "successiva") quindi visualizzare unNULLinvece diMax(ToTime)valore.
Spero che questa spiegazione sia di qualche utilità per le persone. Non so se la mia tecnica di "moltiplicazione di righe" sarà generalmente utile e applicabile alla maggior parte dei writer di query SQL negli ambienti di produzione a causa della difficoltà di comprenderla e della difficoltà di manutenzione che presenterà sicuramente alla prossima persona che visiterà il codice (la reazione è probabilmente "Cosa diavolo sta facendo!?!" seguito da un rapido "È ora di riscrivere!").
Se sei arrivato così lontano, ti ringrazio per il tuo tempo e per avermi concesso la mia piccola escursione nella terra dei puzzle incredibilmente divertente.
Guardalo di persona
Alias simulando un "PREORDER BY":
Un'ultima nota. Per vedere come T - N fa il lavoro, e notando che l'uso di questa parte del mio metodo potrebbe non essere generalmente applicabile alla comunità SQL, esegui la seguente query sulle prime 17 righe dei dati di esempio:
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];
Questo produce:
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
La parte importante è che ogni gruppo di "Walking" o "Running" ha lo stesso valore per T - N che è distinto da qualsiasi altro gruppo con lo stesso nome.
Prestazioni
Non voglio insistere sul fatto che la mia query sia più veloce di quella di altre persone. Tuttavia, data la notevole differenza (quando non ci sono indici), volevo mostrare i numeri in un formato tabella. Questa è una buona tecnica quando sono necessarie prestazioni elevate di questo tipo di correlazione da riga a riga.
Prima dell'esecuzione di ogni query, ho utilizzato DBCC FREEPROCCACHE; DBCC DROPCLEANBUFFERS; . Ho impostato MAXDOP su 1 per ogni query per rimuovere gli effetti di riduzione del tempo del parallelismo. Ho selezionato ogni set di risultati in variabili invece di restituirli al client in modo da misurare solo le prestazioni e non la trasmissione dei dati del client. A tutte le query sono state fornite le stesse clausole ORDER BY. Tutti i test hanno utilizzato 17.408 righe di input ottenendo 8.193 righe di risultati.
Nessun risultato viene visualizzato per le seguenti persone/motivi:
RichardTheKiwi *Could not test--query needs updating*
ypercube *No SQL 2012 environment yet :)*
Tim S *Did not complete tests within 5 minutes*
Senza indice:
CPU Duration Reads Writes
----------- ----------- ----------- -----------
ErikE 344 344 99 0
Simon Kingston 68672 69582 549203 49
Con indice 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
Con indice 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
Quindi la morale della storia è:
Gli indici appropriati sono più importanti della procedura guidata di query
Con l'indice appropriato, la versione di Simon Kingston vince in assoluto, soprattutto quando include la complessità/manutenibilità delle query.
Ascolta bene questa lezione! 38.000 letture non sono molte e la versione di Simon Kingston è stata eseguita in metà del tempo rispetto alla mia. L'aumento di velocità della mia query era interamente dovuto all'assenza di un indice sul tavolo e al concomitante costo catastrofico che questo comportava per qualsiasi query che necessitava di un join (cosa che la mia non aveva):una scansione completa della tabella Hash Match che ne riduceva le prestazioni. Con un indice, la sua query è stata in grado di eseguire un ciclo nidificato con una ricerca di un indice cluster (ovvero una ricerca di segnalibri) che ha reso le cose veramente veloce.
È interessante notare che un indice raggruppato sul solo Tempo non è stato sufficiente. Anche se i tempi erano univoci, il che significava che si verificava un solo nome alla volta, era comunque necessario che il nome facesse parte dell'indice per utilizzarlo correttamente.
L'aggiunta dell'indice cluster alla tabella quando è piena di dati ha richiesto meno di 1 secondo! Non trascurare i tuoi indici.
