Rechercher "ToTime" par agrégats au lieu d'une jointure
Je voudrais partager une requête vraiment sauvage qui ne prend qu'un seul balayage de la table avec une lecture logique. En comparaison, la meilleure autre réponse sur la page, la requête de Simon Kingston, prend 2 scans.
Sur un très grand ensemble de données (17 408 lignes d'entrée, produisant 8 193 lignes de résultat), il faut 574 processeurs et 2 645 temps, tandis que la requête de Simon Kingston utilise 63 820 processeurs et 37 108 temps.
Il est possible qu'avec les index, les autres requêtes de la page fonctionnent bien mieux, mais il est intéressant pour moi d'obtenir une amélioration du processeur 111x et une amélioration de la vitesse 14x simplement en réécrivant la requête.
(Veuillez noter :je ne veux pas manquer de respect à Simon Kingston ou à qui que ce soit d'autre ; je suis tout simplement enthousiasmé par mon idée que cette requête se déroule si bien. Sa requête est meilleure que la mienne car ses performances sont nombreuses et en fait compréhensibles et maintenables , contrairement au mien.)
Voici la requête impossible. C'est difficile à comprendre. C'était difficile à écrire. Mais c'est génial. :)
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
Remarque :Cela nécessite SQL 2008 ou supérieur. Pour le faire fonctionner dans SQL 2005, remplacez la clause VALUES par SELECT 1 UNION ALL SELECT 2 .
Requête mise à jour
Après y avoir un peu réfléchi, j'ai réalisé que j'accomplissais deux tâches logiques distinctes en même temps, ce qui rendait la requête inutilement compliquée :1) élaguer les lignes intermédiaires qui n'ont aucune incidence sur la solution finale (les lignes qui ne commencent pas une nouvelle tâche) et 2) extrayez la valeur "ToTime" de la ligne suivante. En effectuant #1 avant #2, la requête est plus simple et fonctionne avec environ la moitié du CPU !
Voici donc la requête simplifiée qui, d'abord, supprime les lignes dont nous ne nous soucions pas, puis obtient la valeur ToTime en utilisant des agrégats plutôt qu'un JOIN. Oui, il a 3 fonctions de fenêtrage au lieu de 2, mais finalement à cause du moins de lignes (après avoir élagué celles dont nous ne nous soucions pas), il a moins de travail à faire :
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;
Cette requête mise à jour a tous les mêmes problèmes que ceux que j'ai présentés dans mon explication, cependant, ils sont plus faciles à résoudre car je ne traite pas les lignes supplémentaires inutiles. Je vois aussi que le Row_Number() / 2 valeur de 0, j'ai dû exclure, et je ne sais pas pourquoi je ne l'ai pas exclu de la requête précédente, mais en tout cas cela fonctionne parfaitement et est incroyablement rapide !
L'application externe organise les choses
Enfin, voici une version fondamentalement identique à la requête de Simon Kingston qui, je pense, est une syntaxe plus facile à comprendre.
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;
Voici le script de configuration si vous souhaitez effectuer une comparaison des performances sur un ensemble de données plus volumineux :
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
Explication
Voici l'idée de base derrière ma requête.
-
Les heures qui représentent un changement doivent apparaître sur deux lignes adjacentes, une pour mettre fin à l'activité précédente et une pour commencer l'activité suivante. La solution naturelle à cela est une jointure afin qu'une ligne de sortie puisse extraire de sa propre ligne (pour l'heure de début) et la prochaine modification ligne (pour l'heure de fin).
-
Cependant, ma requête répond au besoin de faire apparaître les heures de fin dans deux lignes différentes en répétant la ligne deux fois, avec
CROSS JOIN (VALUES (1), (2)). Nous avons maintenant toutes nos lignes dupliquées. L'idée est qu'au lieu d'utiliser un JOIN pour effectuer des calculs sur plusieurs colonnes, nous utiliserons une forme d'agrégation pour réduire chaque paire de lignes souhaitée en une seule. -
La tâche suivante consiste à diviser correctement chaque ligne en double afin qu'une instance aille avec la paire précédente et une avec la paire suivante. Ceci est accompli avec la colonne T, un
ROW_NUMBER()trié parTime, puis divisé par 2 (bien que je l'ai changé, faites un DENSE_RANK() pour la symétrie car dans ce cas, il renvoie la même valeur que ROW_NUMBER). Pour plus d'efficacité, j'ai effectué la division à l'étape suivante afin que le numéro de ligne puisse être réutilisé dans un autre calcul (continuez à lire). Étant donné que le numéro de ligne commence à 1 et que la division par 2 se convertit implicitement en int, cela a pour effet de produire la séquence0 1 1 2 2 3 3 4 4 ...qui a le résultat souhaité :en regroupant par cette valeur calculée, puisqu'on a aussi ordonné parNumdans le numéro de ligne, nous avons maintenant accompli que tous les ensembles après le premier sont composés d'un Num =2 de la ligne "précédente" et d'un Num =1 de la ligne "suivante". -
La prochaine tâche difficile consiste à trouver un moyen d'éliminer les lignes dont nous ne nous soucions pas et de réduire d'une manière ou d'une autre l'heure de début d'un bloc dans la même ligne que l'heure de fin d'un bloc. Ce que nous voulons, c'est un moyen de faire en sorte que chaque ensemble discret de course ou de marche reçoive son propre numéro afin que nous puissions le regrouper.
DENSE_RANK()est une solution naturelle, mais un problème est qu'il fait attention à chaque valeur dans leORDER BYclause--nous n'avons pas de syntaxe à faireDENSE_RANK() OVER (PREORDER BY Time ORDER BY Name)de sorte que leTimene provoque pas leRANKcalcul à changer sauf à chaque changement deName. Après réflexion, j'ai réalisé que je pouvais m'éloigner un peu de la logique derrière la solution d'îles groupées d'Itzik Ben-Gan, et j'ai compris que le rang des lignes ordonnées parTime, soustrait du rang des lignes partitionnées parNameet classé parTime, donnerait une valeur identique pour chaque ligne du même groupe mais différente des autres groupes. La technique générique des îlots groupés consiste à créer deux valeurs calculées qui montent toutes deux en même temps que les lignes telles que4 5 6et1 2 3, qui, une fois soustrait, donnera la même valeur (dans cet exemple,3 3 3à la suite de4 - 1,5 - 2, et6 - 3). Remarque :J'ai commencé parROW_NUMBER()pour monNcalcul mais ça ne fonctionnait pas. La bonne réponse étaitDENSE_RANK()même si je suis désolé de dire que je ne me souviens pas pourquoi j'ai conclu cela à l'époque, et je devrais plonger à nouveau pour le comprendre. Mais de toute façon, c'est ce queT-Ncalcule :un nombre qui peut être regroupé pour isoler chaque "îlot" d'un statut (soit Course à pied, soit Marche). -
Mais ce n'était pas la fin car il y a quelques rides. Tout d'abord, la ligne "suivante" de chaque groupe contient les valeurs incorrectes pour
Name,N, etT. On contourne cela en sélectionnant, dans chaque groupe, la valeur duNum = 2ligne lorsqu'elle existe (mais si ce n'est pas le cas, nous utilisons la valeur restante). Cela donne des expressions commeCASE WHEN NUM = 2 THEN x END:cela éliminera correctement les valeurs de ligne "suivantes" incorrectes. -
Après quelques expérimentations, je me suis rendu compte qu'il ne suffisait pas de regrouper par
T - Npar lui-même, car les groupes de marche et les groupes de course peuvent avoir la même valeur calculée (dans le cas de mes exemples de données fournis jusqu'à 17, il y a deuxT - Nvaleurs de 6). Mais simplement en regroupant parNamerésout également ce problème. Aucun groupe de "Courir" ou "Marcher" n'aura le même nombre de valeurs intermédiaires du type opposé. Autrement dit, puisque le premier groupe commence par "Running", et qu'il y a deux lignes "Walking" intervenant avant le prochain groupe "Running", alors la valeur de N sera inférieure de 2 à la valeur deTdans ce prochain groupe "Courir". Je viens de réaliser qu'une façon de penser à cela est que leT - Ncalcul compte le nombre de lignes avant la ligne actuelle qui n'appartiennent PAS à la même valeur "Courir" ou "Marcher". Une certaine réflexion montrera que c'est vrai :si nous passons au troisième groupe "Courir", ce n'est que le troisième groupe en raison du fait qu'un groupe "Marche" les sépare, il a donc un nombre différent de rangées intermédiaires entrant avant, et du fait qu'il commence à une position plus élevée, il est suffisamment élevé pour que les valeurs ne puissent pas être dupliquées. -
Enfin, puisque notre groupe final se compose d'une seule ligne (il n'y a pas d'heure de fin et nous devons afficher un
NULLà la place) j'ai dû faire un calcul qui pourrait être utilisé pour déterminer si nous avions une heure de fin ou non. Ceci est accompli avec leMin(Num)expression et enfin détecter que lorsque Min(Num) était 2 (ce qui signifie que nous n'avions pas de ligne "suivante") puis afficher unNULLau lieu duMax(ToTime)valeur.
J'espère que cette explication sera utile aux gens. Je ne sais pas si ma technique de "multiplication de lignes" sera généralement utile et applicable à la plupart des rédacteurs de requêtes SQL dans des environnements de production en raison de la difficulté à la comprendre et de la difficulté de maintenance qu'elle présentera très certainement à la prochaine personne visitant le code (la réaction est probablement "Qu'est-ce qu'il fait !?!" suivi d'un rapide "Il est temps de réécrire !").
Si vous êtes arrivé jusqu'ici, je vous remercie de votre temps et de m'avoir permis de participer à ma petite excursion dans un monde de puzzles sql incroyablement amusant.
Voyez-le par vous-même
Alias. simulant une "PRECOMMANDE PAR":
Une dernière note. Pour voir comment T - N fait le travail - et notant que l'utilisation de cette partie de ma méthode peut ne pas être généralement applicable à la communauté SQL - exécutez la requête suivante sur les 17 premières lignes des exemples de données :
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];
Cela donne :
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
L'important étant que chaque groupe de "Marche" ou "Course" ait la même valeur pour T - N distinct de tout autre groupe portant le même nom.
Performances
Je ne veux pas insister sur le fait que ma requête est plus rapide que celle des autres. Cependant, étant donné à quel point la différence est frappante (lorsqu'il n'y a pas d'index), je voulais afficher les chiffres sous forme de tableau. Il s'agit d'une bonne technique lorsque des performances élevées de ce type de corrélation ligne à ligne sont nécessaires.
Avant l'exécution de chaque requête, j'ai utilisé DBCC FREEPROCCACHE; DBCC DROPCLEANBUFFERS; . J'ai défini MAXDOP sur 1 pour chaque requête afin de supprimer les effets d'effondrement temporel du parallélisme. J'ai sélectionné chaque jeu de résultats dans des variables au lieu de les renvoyer au client afin de mesurer uniquement les performances et non la transmission des données du client. Toutes les requêtes ont reçu les mêmes clauses ORDER BY. Tous les tests ont utilisé 17 408 lignes d'entrée, ce qui a donné 8 193 lignes de résultats.
Aucun résultat n'est affiché pour les personnes/raisons suivantes :
RichardTheKiwi *Could not test--query needs updating*
ypercube *No SQL 2012 environment yet :)*
Tim S *Did not complete tests within 5 minutes*
Sans index :
CPU Duration Reads Writes
----------- ----------- ----------- -----------
ErikE 344 344 99 0
Simon Kingston 68672 69582 549203 49
Avec l'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
Avec l'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
Donc la morale de l'histoire est :
Des index appropriés sont plus importants que l'assistant de requête
Avec l'index approprié, la version de Simon Kingston gagne dans l'ensemble, en particulier si l'on tient compte de la complexité/maintenabilité des requêtes.
Tenez bien compte de cette leçon ! 38 000 lectures, ce n'est pas vraiment beaucoup, et la version de Simon Kingston a duré deux fois moins de temps que la mienne. L'augmentation de la vitesse de ma requête était entièrement due à l'absence d'index sur la table, et au coût catastrophique concomitant que cela a donné à toute requête nécessitant une jointure (ce que la mienne n'a pas fait):une analyse complète de la table Hash Match tuant ses performances. Avec un index, sa requête était capable de faire une boucle imbriquée avec une recherche d'index groupé (c'est-à-dire une recherche de signet) qui rendait les choses vraiment rapide.
Il est intéressant de noter qu'un index groupé sur le temps seul n'était pas suffisant. Même si les heures étaient uniques, ce qui signifie qu'un seul nom apparaissait à la fois, il fallait toujours que le nom fasse partie de l'index afin de l'utiliser correctement.
L'ajout de l'index clusterisé à la table lorsqu'elle était pleine de données a pris moins d'une seconde ! Ne négligez pas vos index.
