问题
当某人带着真正不可能的要求来到我们身边时，我们所有人都在工作，而要实现这一要求则需要奇迹。我的案例发生在一位营销同事向我提出一个看似简单的问题时：几年前我是否可以从某个表中获取某个月的数据。您不能说错，但我隐约记得桌子很大。该表具有带有创建时间的datetime字段，但是此字段上有索引吗？
当然，他们也想快速获取数据。像往常一样，我说：“我会看看我能做些什么。”，然后仔细研究了正在讨论的表格。祝您好运永远不会离开我们，索引确实不存在，并且表格很大。没问题，我们可以扫描桌子，对吧？错误。如果我从使用数据库的那几年中学到了什么，那就重要了。一个包含数亿条记录（由几个整数列组成）的表将非常强大。然后添加各种varchar和datetime列。现在这是一个真正的挑战，不是吗？
实际上，我正在查看的表有十亿条记录。一个简单的表扫描可能很容易花费一天的时间，因此我也需要处理提取的数据。另外，扫描这种大小的表可能不像乍看起来那样有利于系统的一般状态。应该通过将所有扫描的页面从磁盘中提取到sql服务器内存中。反过来，这将从缓存中卸载数据页，这些数据页可用于当前的操作任务。当服务器从磁盘重新读取数据时，当前用户的请求可能会等待更长的时间，而不是快速重新使用内存中的数据页。性能可能会下降，在最坏的情况下，服务器可能会完全屈服。从而，扫描表格时，应该使用一种特殊的技术-小批量运行它，将当前位置和中间结果保留在某个位置。这种方法允许服务器重新配置并喘口气，而不会影响性能。
因此，当我想到创建时间的datetime值与表标识符相关联时，我考虑了场景并估计了启动和执行脚本所需的时间。标识符（ID）是一列不断增加的值和基于它的主键。按标识符获取时，创建日期和时间值自然会按照与标识符值相同的方式进行预排序。等等，我想，我可以实现比表扫描快得多的东西，在最坏的情况下，它只需30步，而不是500,000,000！二进制搜索！
搜索
对于像我一样早就完成学业的每个人，理论上的再训练都应该按顺序进行。二进制搜索是一种在排序数组中（在我们的情况下是在表列中）搜索值的简单但极其有效的方法。数组必须是预排序且有限的。通过将数组的中间元素与目标进行比较来完成搜索。如果它们相等，则搜索结束。如果不是，则删除明显缺少所需元素的那一半，然后重复上一步，直到只剩下一个。找到中间，与目标进行比较，如果目标不相等，则再去除一半，依此类推。在最坏情况下找到目标所需的总步数为log（N），其中N是元素数。将此与N / 2进行比较当您仅遍历数组时。一般而言，这将是N，但是如果我们可以猜测目标是否接近终点，我们可以返回，从而减少所需步骤的总数。
在我的情况下，N = 1,000,000,000，这就是我得出上述两个数字的方式：30和500,000,000。该ID将充当数组枚举器的角色，而创建日期时间将是该数组元素的值。尽管有一个警告。就其定义而言，数组枚举器是连续的整数顺序序列。由于删除记录或重新填充标识符，表标识符中很容易出现空格。通过将标识符的范围除以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用于迭代过程，因为在这种情况下，ID值中有空格，并且在某些情况下，该算法可能会陷入无限循环。
我花了大约一个小时来编写和测试脚本。使用它，我找到了具有特定创建日期和时间的第一条记录。之后，我使用了一个简单的select语句，其中包含两个条件的where子句：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)