問題
誰かが本当に不可能な要件を持って私たちのところに来るとき、私たち全員が仕事をしていて、その実現には奇跡が必要です。私のケースは、マーケティングの同僚が一見単純な質問で私に近づいたときに起こりました：数年前に特定の月の1つのテーブルからデータを取得できるかどうか。何も悪いことは言えませんが、テーブルが非常に大きいことを漠然と思い出しました。テーブルには作成時の日時フィールドがありましたが、そのフィールドにインデックスがありましたか？
もちろん、データをすばやく取得することも望んでいました。いつものように、「何ができるか見てみよう」と言って、議論中の表をよく見に行きました。幸運は私たちを離れることはなく、インデックスは実際には存在せず、テーブルは巨大でした。問題ありません、テーブルをスキャンできますよね？違う。長年にわたってデータベースを操作していて何かを学んだとしたら、それはサイズが重要であることです。何億ものレコードといくつかの整数列を含むテーブルは、手ごわいものになるでしょう。次に、さまざまなvarchar列とdatetime列を追加します。さて、それは本当の挑戦ですよね。
私が見ていたテーブルには、文字通り10億件のレコードがありました。単純なテーブルスキャンでは1日以上かかる場合があり、抽出したデータも処理する必要がありました。さらに、このサイズのテーブルをスキャンすることは、一見したようにシステムの一般的な状態に適しているとは限りません。スキャンされたすべてのページは、ディスクからSQLサーバーのメモリに入力して抽出する必要があります。これにより、キャッシュからデータページがアンロードされ、現在の運用タスクに使用できます。現在のユーザーからのリクエストは、サーバーがメモリからデータページをすぐに再利用するのではなく、サーバーがディスクからデータを再読み込みする間、より長く待機する場合があります。パフォーマンスが低下する可能性があり、最悪の場合、サーバーが完全に機能しなくなる可能性があります。したがって、テーブルをスキャンするときは、特別な手法を使用する必要があります。現在の位置と中間結果をどこかに保持して、小さなバッチで実行します。このアプローチにより、サーバーを再構成してブリーザーを設定できるため、パフォーマンスの大幅な低下を回避できます。
そして、私は作業のシナリオについて考え、作成時間の日時値がテーブルIDに関連付けられていることが発生したときにスクリプトを実行して実行するのにかかる時間を見積もりました。識別子（ID）は、絶えず増加する値とそれに基づく主キーを持つ列でした。識別子で選択する場合、作成日時の値は、識別子の値と同じ方法で自然に事前に並べ替えられました。ちょっと待って、テーブルをスキャンするよりも非常に高速なものを実装できると思いました。最悪の場合、500,000,000ではなく30ステップしか必要ありません。バイナリ検索！
探す
私のように、ずっと前にトレーニングを卒業したすべての人にとって、理論的には再トレーニングが順調に行われるべきです。バイナリ検索は、並べ替えられた配列（この場合はテーブル列）の値を見つけるための単純ですが非常に効率的な方法です。配列は事前にソートされ、有限でなければなりません。検索は、配列の中央の要素をターゲットと比較することによって行われます。それらが等しい場合、検索は終了です。そうでない場合は、探している要素が明らかに欠落している半分を削除し、1つがなくなるまで前の手順を繰り返します。真ん中を見つけ、ターゲットをそれと比較し、それらが等しくない場合は、半分を再度削除します。最悪の場合にゴールを見つけるために必要なステップの総数は、最後のステップでそれを見つけた場合、log（N）です。ここで、Nは要素の数です。これをN / 2と比較してください配列を反復するだけです。一般的に言えば、これはNですが、ゴールが最後に近いかどうかを推測できれば、戻ることができ、必要なステップの総数を減らすことができます。
私の場合、N = 1,000,000,000であり、これが上記の2つの数値、30と500,000,000に到達した方法です。 IDは配列列挙子の役割を果たし、作成日時は配列要素の値になります。ただし、注意点が1つあります。配列列挙子は、まさにその定義により、整数の連続したシーケンスです。レコードの削除または識別子の再入力が原因で、テーブル識別子にスペースが含まれる可能性があります。識別子の範囲を2で除算することで中央を決定するだけで、そのような識別子を持つエントリが存在することを期待するべきではありません。直接検索する代わりに、top（）関数を使用する必要がありました。そんな感じ：
Select top(1) * from Table where id <= @id order by id desc「<=」と「desc」を使用したのは、ターゲットと等しいか、ターゲットの直前の値を見つけたかったためです。@ l、@ rはそれぞれ左と右の境界です。id 真ん中、@ dtは作成日時、 tdt 目標であり、 idrは実際のテーブル識別子（ID）であり、アルゴリズムは次のようになります。
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
最終発見 idrは、目的のエントリが後に続くエントリの識別子です。アルゴリズムには「左」シフトのようなものがあります。つまり、すべての値の左端を選択する傾向があります。値を持つレコードをできるだけターゲットに近づけたいので、テーブルの最も近い左右の隣人もチェックして、どちらかが優れているかどうかを確認しました。この場合、ID値にスペースが含まれているため、反復処理にテーブルの実際の識別子を使用しなかったことに注意してください。状況によっては、アルゴリズムが無限ループに入る可能性があります。
スクリプトの作成とテストに約1時間かかりました。それを使用して、特定の作成日時を持つ最初のレコードを見つけました。その後、両方の条件を含むwhere句を含む簡単なselectステートメントを使用しました：id> = @およびcreation_datetime> = @ dt1およびcreation_datetime <@ dt2。オプティマイザがインデックスまたはテーブルスキャンの代わりに主キーを使用することを選択することを確認する必要があるだけでした。全体として、私は2時間未満でそれを行いました！アルゴリズムがSQLサーバーの奥深くに埋め込まれた難解なものではなく、日常の作業で簡単に使用できるものであることを再度発見したのは驚きでした。
以下は私が書いたスクリプト全体です。使い方は、コメント欄をご覧ください。
/*
, .
, 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)