如何在特定字段SQL中使用已知数据顺序的表进行二进制搜索

Question

我有一个像这样结构的表:

create table to_much_data
(
    id primary key clustered,
    dt datetime,
    data varbinary(400)
)

它没有按日期时间的索引,但我知道dt非递减序列.我需要查询此表中的数据,具有特定条件的日期字段,如下所示:

select * 
from to_much_data
where dt between '20190220' and '20190221'

因为没有dt的索引,我更喜欢将查询转换为:

select * 
from to_much_data
where id between StartDateID and EndDateID 

我相信StartDateID并且EndDateID可以找到log(N)或更好的复杂性.但我不知道有任何解决办法.

有没有人知道这样做的方法？

UPD

看起来没有广为人知的即用型解决方案.如果无法创建索引,可以使用一些变通方法:

• 过滤索引,但它可以影响表性能并增加锁定
• 另一个带映射的表,但需要手动更新(或通过触发器或存储过程),它可能会影响性能并增加锁定
• t-sql代码与傻二进制搜索,但它看起来像自行车重塑

尽管如此,我相信在某些情况下,数据库可以更加有效和直观.如果有一天我们能够写下来,我会很高兴的:

select * 
from to_much_data with(sequence_order(id asc, dt asc))
where dt between '20190220' and '20190221'

Answer 1

您可以在TSQL中重现二进制搜索算法或使用递归CTE,但这仍然需要超过70次搜索以获得两端并且执行起来很繁琐.

可能的中间地点可能是创建至少每第n行的索引视图.例如

CREATE VIEW dbo.to_much_data_Sample
WITH SCHEMABINDING
AS
  SELECT id,
         dt
  FROM   dbo.to_much_data
  WHERE  id % 100000 = 0

GO

CREATE UNIQUE CLUSTERED INDEX ix
  ON dbo.to_much_data_Sample(dt, id);

然后你可以使用(假设id是一个整数)

DECLARE @StartDate DATETIME = '20190220',
        @EndDate   DATETIME = '20190221';

DECLARE @StartDateID INT,
        @EndDateID   INT;

SELECT TOP 1 @StartDateID = id
FROM   dbo.to_much_data_Sample WITH (NOEXPAND)
WHERE  dt < @StartDate
ORDER  BY dt DESC;

SELECT TOP 1 @EndDateID = id
FROM   dbo.to_much_data_Sample WITH (NOEXPAND)
WHERE  dt > @EndDate
ORDER  BY dt ASC;

SELECT *
FROM   to_much_data
WHERE  id BETWEEN isnull(@StartDateID, -2147483648) AND isnull(@EndDateID, 2147483647)
       AND dt BETWEEN @StartDate AND @EndDate; 

值n将在索引大小和运行时读取的其他行数之间进行权衡.

Answer 2

很明显，您不能在数据列上创建索引。

不清楚的是表中的其余列及其数据类型以及真正的搜索将是什么样子？

因为这很重要。

无论我理解什么，它都不是候选者Filtered Index，我的意思是日期范围不是好的候选者Filtered Index。

顺便说一句，如果您能想到过滤索引那么为什么不在日期列上创建索引？

范围搜索对于两者来说都不理想Binary Search，尤其是在 Sql 服务器中。

如果我错了，请纠正我。

SET NoCount on

declare @StartDateID int
declare @EndDateID int

select @StartDateID=min(id), @EndDateID=max(id)
from dbo.to_much_data
where dt between '20190220' and '20190221'

select id,dt,[data]
from to_much_data
where id >= @StartDateID and id <= @EndDateID 

它可能是一个很好的候选者，Partition但我们需要知道其他细节，例如有多少行？

数据从哪个源填充以及一次可以插入多少行？

插入/更新数据的频率如何？

编辑 ：

样本数据，

SET STATISTICS XML OFF
SET NOCOUNT ON;
DECLARE
    @i  INTEGER = 1,
    @s  FLOAT = RAND(20120104),
    @e  FLOAT = RAND();
    declare @jj datetime='2009-01-01'
WHILE @i <= 1000000
BEGIN
        if(@i=1000000 or @i=2000000)
        set @jj=dateadd(year,1,@jj)

    INSERT dbo.SomeDateTable
        (
        StartDate, 
        vdata
        )
    VALUES
        (
        DATEADD(DAY, @s * 365, @jj),
       cast(REPLICATE('A',500) as varbinary(500))
        )

    SELECT
        @s = RAND(),
        @e = RAND(),
        @i += 1
END

您可以检查我的示例中的日期范围分布，并更正日期范围并回发。

declare @SDate datetime='2009-07-11'
declare @EDate datetime='2012-12-30'
declare @Sid int
declare @Eid int

--select * from dbo.SomeDateTable
--where StartDate>=@SDate and StartDate<=@EDate

Above query give Table Scan  

select @Sid=min(id) ,@Eid=max(id) from dbo.SomeDateTable
where StartDate>=@SDate and StartDate<=@EDate

该查询提供了 2 次索引扫描，但子查询成本非常低

select @Sid,@Eid
select id,StartDate,vdata from dbo.SomeDateTable
where id>=@Sid and id<=@Eid

该查询是索引查找

在给定的条件下我对此非常确定