Problème
Nous avons tous des jours de travail où quelqu'un vient à nous avec une exigence vraiment impossible, dont l'accomplissement nécessite un miracle. Mon cas s'est produit lorsqu'un collègue en marketing m'a posé une question apparemment simple: si je pouvais obtenir des données d'une table pendant un certain mois il y a quelques années. Vous ne pouvez rien dire de mal, mais je me souviens vaguement que la table était très grande. La table avait un champ datetime avec l'heure de création, mais y avait-il un index sur ce champ?
Bien sûr, ils voulaient également obtenir les données rapidement. Comme d'habitude, j'ai dit: «Je vais voir ce que je peux faire», et je suis allé regarder de plus près la table en discussion. La chance ne nous quittera jamais, l'index n'existait vraiment pas et la table était énorme. Pas de problème, on peut scanner le tableau, non? Faux. Si j'ai appris quelque chose des années de travail avec les bases de données, c'est que la taille compte. Un tableau avec des centaines de millions d'enregistrements et plusieurs colonnes entières serait assez formidable. Ajoutez ensuite diverses colonnes varchar et datetime. Maintenant, c'est un vrai défi, non?
Le tableau que je regardais contenait un milliard d'enregistrements, littéralement. Une simple analyse de table pouvait facilement prendre plus d'une journée et je devais également traiter les données extraites. En outre, la numérisation d'une table de cette taille peut ne pas être aussi bénéfique pour la santé globale du système qu'il n'y paraît à première vue. Toutes les pages numérisées doivent être extraites des disques dans la mémoire SQL du serveur, en la remplissant. Ceci, à son tour, déchargera les pages de données du cache, qui peuvent être utilisées pour les tâches opérationnelles actuelles. Les demandes de vos utilisateurs actuels peuvent attendre plus longtemps pendant que le serveur relit les données des disques, plutôt que de réutiliser rapidement les pages de données de la mémoire. Les performances peuvent être dégradées et dans le pire des cas, le serveur peut être complètement mis à genoux. Donc,lors de la numérisation d'une table, vous devez utiliser une technique spéciale - l'exécuter par petits lots, en conservant la position actuelle et les résultats intermédiaires quelque part. Cette approche permet au serveur de se reconfigurer et d'avoir une pause sans autoriser un impact important sur les performances.
Et donc je pensais au scénario de travail et à l'estimation du temps qu'il faudrait pour exécuter et exécuter le script quand il m'est venu à l'esprit que les valeurs datetime de l'heure de création étaient associées à l'ID de la table. L'identifiant (ID) était une colonne avec des valeurs en constante augmentation et une clé primaire basée sur elle. Lors de la sélection par identifiant, les valeurs de date et d'heure de création ont naturellement été pré-triées de la même manière que les valeurs d'identifiant. Attendez, je pensais, je pourrais implémenter quelque chose d'extrêmement rapide qu'une analyse de table, quelque chose qui dans le pire des cas ne prendrait que 30 étapes au lieu de 500 000 000! Recherche binaire!
Chercher
Pour tous ceux qui, comme moi, sont diplômés de la formation depuis longtemps, le recyclage en théorie devrait être dans l'ordre des choses. La recherche binaire est un moyen simple mais extrêmement efficace de trouver une valeur dans un tableau trié (dans notre cas, une colonne de table). Le tableau doit être pré-trié et fini. La recherche est effectuée en comparant l'élément central de votre tableau avec la cible. S'ils sont égaux, la recherche est terminée. Sinon, vous supprimez la moitié dans laquelle l'élément souhaité est manifestement absent, et répétez l'étape précédente jusqu'à ce qu'il n'en reste plus qu'un. Trouvez le milieu, comparez la cible avec elle, si elles ne sont pas égales, retirez à nouveau la moitié et ainsi de suite. Le nombre total d'étapes nécessaires pour trouver la cible dans le pire des cas, lorsque vous la trouverez à la toute dernière étape, sera log (N), où N est le nombre d'éléments. Comparez cela à N / 2,lorsque vous parcourez simplement un tableau. D'une manière générale, ce serait N, mais si nous pouvions deviner si l'objectif est plus proche de la fin, nous pourrions revenir en arrière, réduisant ainsi le nombre total d'étapes nécessaires.
Dans mon cas, N = 1 000 000 000 et c'est ainsi que j'en suis arrivé aux deux chiffres ci-dessus: 30 et 500 000 000. Un identifiant (ID) jouerait le rôle d'un énumérateur de tableau et la date / heure de création serait la valeur de l'élément de tableau. Il y a cependant une mise en garde. Un énumérateur de tableau, par définition, est une séquence séquentielle continue d'entiers. Il est facile pour les ID de table de contenir des espaces en raison de la suppression d'enregistrements ou d'un dépassement d'ID. En déterminant simplement le milieu en divisant la plage d'identifiants par 2, vous ne devez pas vous attendre à ce qu'il y ait une entrée avec un tel identifiant. Au lieu de chercher directement, j'ai dû utiliser la fonction top (). Quelque chose comme ca:
Select top(1) * from Table where id <= @id order by id descJ'ai utilisé «<=» et «desc» parce que je voulais trouver une valeur égale ou immédiatement avant l'objectif. Sous la condition @l, @r est respectivement les bordures gauche et droite,id Est le milieu, @dt est le datetime de création, tdt Est le but et idr identifiant de table réel (ID), l'algorithme peut ressembler à ceci:
while @l <@r
begin
--
@id = @l +floor((@r-@l)/2)
--
select top(1) @idr = id, @dt = creation_datetime from Table where id <= @id order by id desc
--
if(@dt<@tdt)
@l = @id +1
else
@r = @id
end
Dernier trouvé idr serait l'identifiant de l'entrée suivi de celui souhaité. L'algorithme a quelque chose comme un décalage «à gauche», c'est-à-dire une tendance à choisir la plus à gauche de toutes les valeurs. Puisque je voulais que l'enregistrement avec la valeur soit aussi proche que possible de la cible, j'ai également vérifié les voisins gauche et droit les plus proches dans le tableau pour voir si l'un d'eux était meilleur. Veuillez noter que je n'ai pas utilisé l'identifiant réel de la table pour le processus d'itération, comme dans ce cas, avec des espaces dans les valeurs d'identifiant et dans certaines circonstances, l'algorithme pourrait entrer dans une boucle infinie.
Il m'a fallu environ une heure pour écrire et tester le script. En l'utilisant, j'ai trouvé la première entrée avec une date et une heure de création spécifiques. Après cela, j'ai utilisé une simple instruction select avec une clause where contenant les deux conditions: id> = @ et creation_datetime> = @ dt1 et creation_datetime <@ dt2. Je devais simplement m'assurer que l'optimiseur choisirait d'utiliser la clé primaire au lieu d'un index ou d'une analyse de table. Dans l'ensemble, je l'ai fait en moins de 2 heures! Il était surprenant de découvrir à nouveau que les algorithmes ne sont pas quelque chose d'ésotérique enfoui profondément dans le serveur SQL, mais plutôt quelque chose qui peut être facilement utilisé dans le travail quotidien.
Vous trouverez ci-dessous l'intégralité du script que j'ai écrit. Veuillez consulter les commentaires à l'intérieur pour comprendre comment l'utiliser.
/*
, .
, datetime 3
*/
-- , ,
declare @debug bit = 0
-- @Table - , .
declare @Table varchar(128) = 'TableX'
-- @Id - (id)
declare @ID varchar(128) = 'Id'
-- @DateTimeColumn - datetime
declare @DateTimeColumn varchar(128) = 'created_dt'
--
declare @TargetDateTime datetime = '2020-01-03 18:23:03'
declare @Sql varchar(max)
set @sql = '
--
declare @debug bit = <debug>
--
declare @tdt datetime = ''<TargetDateTime>''
-- ( )
declare @id bigint
--
declare @l bigint, @r bigint
-- , , datetime
declare @dt datetime, @idr bigint
-- «» «»
select @l = min(<ID>), @r = max(<ID>) from <Table>
while @l < @r
begin
--
set @id = @l +floor((@r-@l)/2)
--
select top(1) @dt = <DateTimeColumn>, @idr = <ID> from <Table> where <ID> <= @id order by <ID> desc
-- ,
if( @debug = 1 )
begin
select ''@id'' = @id, ''@l'' = @l, ''@r'' = @r, ''@dt'' = @dt, ''@idr'' = @idr
end
if(@dt < @tdt)
set @l = @id +1
else
set @r = @id
end
-- ,
declare @t table(id bigint, dt datetime, dlt float)
insert @t(id, dt, dlt)
select top(1) <ID>, <DateTimeColumn>, abs(cast(<DateTimeColumn> as float) -cast(@tdt as float))
from <Table>
where <ID> < @idr
order by <ID> desc
insert @t(id, dt, dlt)
select top(1) <ID>, <DateTimeColumn>, abs(cast(<DateTimeColumn> as float) -cast(@tdt as float))
from <Table>
where <ID> > @idr
order by <ID>
insert @t(id, dt, dlt)
select @idr, @dt, abs(cast(@dt as float) -cast(@tdt as float))
select top(1) @dt = dt, @idr = id from @t order by dlt, id
select ''Found Value'' = @dt, ''Record Id'' = @idr
'
set @sql = replace(
replace(
replace(
replace(
replace(@sql, '<ID>', @ID),
'<Table>', @Table),
'<TargetDateTime>', convert(varchar(50), @TargetDateTime, 121)),
'<debug>', @debug),
'<DateTimeColumn>', @DateTimeColumn)
exec (@sql)