Problem
Wir alle haben Arbeitstage, an denen jemand mit einer wirklich unmöglichen Anforderung zu uns kommt, deren Erfüllung ein Wunder erfordert. Mein Fall ereignete sich, als ein Marketingkollege mit einer scheinbar einfachen Frage auf mich zukam: ob ich vor ein paar Jahren für einen bestimmten Monat Daten von einer Tabelle erhalten könnte. Es ist okay, könnte man sagen, aber ich erinnerte mich vage daran, dass der Tisch sehr groß war. Die Tabelle hatte zum Zeitpunkt der Erstellung ein Datum / Uhrzeit-Feld, aber gab es einen Index für dieses Feld?
Natürlich wollten sie auch die Daten schnell bekommen. Ich sagte wie immer: „Ich werde sehen, was ich tun kann“ und schaute mir den diskutierten Tisch genauer an. Das Glück verlässt uns nie, der Index existierte nicht wirklich und die Tabelle war riesig. Kein Problem, wir können die Tabelle scannen, oder? Falsch. Wenn ich über die Jahre der Arbeit mit Datenbanken etwas gelernt habe, dann ist es die Größe, die zählt. Eine Tabelle mit Hunderten von Millionen Datensätzen und mehreren ganzzahligen Spalten wäre beeindruckend genug. Fügen Sie dann verschiedene varchar- und datetime-Spalten hinzu. Das ist eine echte Herausforderung, nicht wahr?
Der Tisch, den ich betrachtete, hatte buchstäblich eine Milliarde Datensätze. Ein einfacher Tabellenscan könnte leicht über einen Tag dauern, und ich musste auch die extrahierten Daten verarbeiten. Darüber hinaus ist das Scannen einer Tabelle dieser Größe für den allgemeinen Zustand des Systems möglicherweise nicht so günstig, wie es auf den ersten Blick erscheint. Alle gescannten Seiten sollten durch Ausfüllen von den Datenträgern in den SQL Server-Speicher extrahiert werden. Dadurch werden wiederum Datenseiten aus dem Cache entladen, die für aktuelle Betriebsaufgaben verwendet werden können. Die Anforderungen Ihrer aktuellen Benutzer warten möglicherweise länger, während der Server Daten von Datenträgern erneut liest, anstatt Datenseiten aus dem Speicher schnell wiederzuverwenden. Die Leistung kann beeinträchtigt werden, und im schlimmsten Fall kann der Server vollständig in die Knie gezwungen werden. Auf diese Weise,Wenn Sie eine Tabelle scannen, sollten Sie eine spezielle Technik anwenden - führen Sie sie in kleinen Stapeln aus und behalten Sie dabei die aktuelle Position und die Zwischenergebnisse bei. Dieser Ansatz ermöglicht es dem Server, sich neu zu konfigurieren und eine Verschnaufpause einzulegen, ohne einen großen Leistungseinbruch zuzulassen.
Daher dachte ich über das Szenario nach und schätzte die Zeit, die zum Starten und Ausführen des Skripts benötigt wurde, als mir einfiel, dass die Datums- / Uhrzeitwerte der Erstellungszeit mit der Tabellenkennung verknüpft waren. Der Bezeichner (ID) war eine Spalte mit ständig wachsenden Werten und einem darauf basierenden Primärschlüssel. Bei der Auswahl nach Bezeichner wurden die Werte für Erstellungsdatum und -zeit natürlich auf die gleiche Weise wie die Bezeichnerwerte vorsortiert. Warten Sie, dachte ich, ich kann etwas extrem schnelles realisieren, als einen Tisch zu scannen, was im schlimmsten Fall nur 30 Schritte anstelle von 500.000.000 erfordern würde! Binäre Suche!
Suche
Für alle, die wie ich vor langer Zeit die Ausbildung abgeschlossen haben, sollte die theoretische Umschulung in der Reihenfolge der Dinge liegen. Die binäre Suche ist eine einfache, aber äußerst effiziente Methode, um einen Wert in einem sortierten Array (in unserem Fall einer Tabellenspalte) zu finden. Das Array muss vorsortiert und endlich sein. Die Suche wird durchgeführt, indem das mittlere Element Ihres Arrays mit dem Ziel verglichen wird. Wenn sie gleich sind, ist die Suche beendet. Wenn nicht, löschen Sie die Hälfte, in der das gesuchte Element offensichtlich fehlt, und wiederholen den vorherigen Schritt, bis Sie eines haben. Finde die Mitte, vergleiche das Ziel damit. Wenn sie nicht gleich sind, entferne die Hälfte wieder und so weiter. Die Gesamtzahl der Schritte, die erforderlich sind, um das Ziel im schlimmsten Fall zu finden, wenn Sie es im allerletzten Schritt finden, ist log (N), wobei N die Anzahl der Elemente ist. Vergleichen Sie dies mit N / 2,wenn Sie nur über das Array iterieren. Im Allgemeinen wäre dies N, aber wenn wir erraten könnten, ob das Ziel näher am Ende liegt, könnten wir zurückgehen und dadurch die Gesamtzahl der erforderlichen Schritte reduzieren.
In meinem Fall ist N = 1.000.000.000 und so bin ich zu den beiden obigen Zahlen gekommen: 30 und 500.000.000. Die ID würde die Rolle eines Array-Enumerators spielen, und die Erstellungsdatumzeit wäre der Wert des Array-Elements. Obwohl es eine Einschränkung gibt. Ein Array-Enumerator ist per Definition eine kontinuierliche sequentielle Folge von ganzen Zahlen. Tabellen-IDs können aufgrund von Datensatzlöschung oder ID-Überlauf leicht Leerzeichen enthalten. Wenn Sie einfach die Mitte bestimmen, indem Sie den Bereich der Bezeichner durch 2 teilen, sollten Sie nicht erwarten, dass es einen Eintrag mit einem solchen Bezeichner gibt. Anstatt direkt zu suchen, musste ich die Funktion top () verwenden. Sowas in der Art:
Select top(1) * from Table where id <= @id order by id descIch habe "<=" und "desc" verwendet, weil ich einen Wert finden wollte, der entweder gleich oder unmittelbar vor dem Ziel ist. Vorausgesetzt, @l, @r sind linke bzw. rechte Ränder.Ich würde Ist die Mitte, @dt ist das Erstellungsdatum, tdt Ist das Ziel und Ich würdeBei einer echten Tabellenkennung (ID) kann der Algorithmus folgendermaßen aussehen:
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
Zuletzt gefunden Ich würder wäre die Kennung des Eintrags, gefolgt von dem gewünschten. Der Algorithmus hat eine Art "linken" Versatz, dh eine Tendenz, von allen Werten ganz links zu wählen. Da ich wollte, dass der Wertdatensatz so nah wie möglich am Ziel ist, überprüfte ich auch die nächsten linken und rechten Nachbarn in der Tabelle, um festzustellen, ob einer besser war. Bitte beachten Sie, dass ich den realen Bezeichner aus der Tabelle nicht für den Iterationsprozess verwendet habe, wie in diesem Fall mit Leerzeichen in den ID-Werten, und unter bestimmten Umständen könnte der Algorithmus in eine Endlosschleife gehen.
Ich habe ungefähr eine Stunde gebraucht, um das Skript zu schreiben und zu testen. Damit habe ich den ersten Eintrag mit einem bestimmten Erstellungsdatum und einer bestimmten Erstellungszeit gefunden. Danach habe ich eine einfache select-Anweisung mit einer where-Klausel verwendet, die beide Bedingungen enthielt: id> = @ und kreationsdatenzeit> = @ dt1 und kreationsdatenzeit <@ dt2. Ich musste nur sicherstellen, dass das Optimierungsprogramm einen Primärschlüssel anstelle eines Index- oder Tabellenscans verwendet. Alles in allem habe ich es in weniger als 2 Stunden geschafft! Es war überraschend wieder zu entdecken, dass die Algorithmen nicht etwas Esoterisches sind, das tief im SQL Server vergraben ist, sondern etwas, das leicht in der täglichen Arbeit verwendet werden kann.
Unten ist das gesamte Skript, das ich geschrieben habe. Bitte lesen Sie die Kommentare im Inneren, um zu verstehen, wie man es benutzt.
/*
, .
, 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)