Поиск столбца с помощью двоичного поиска на основе другого кластерного столбца - SQL Server Query

Question

Сая, у меня есть конкатенирующая только аудиторская таблица со следующей схемой:

ColumnX, AuditRowId, AuditDTim 
CLUSTERED INDEX ON AuditRowId 

Как написать «производительный» запрос SQL Server для найдите COUNT(*) строк между конкретными значениями AuditDTim?

Эти ограничения:

• Я хочу использовать SQL. Не переносить данные на платформы BigData.
• Мы не можем сменить кластеризованный индекс на AuditDTim. Предположим, что legacyDb не имеет доступа к DDL.
• Мы не можем добавить новый индекс к AuditDTim.
• Предположим, что это очень большая таблица с миллиардами записей
• Отношение между AuditRowId и AuditDTim - оба сметный характер, то есть, как AuditRowId увеличивается, AuditDTim либо увеличивается или остается неизменной.

Answer 1

Предположительно, вы бы использовать запрос, как это:

select count(*) 
from audi 
where auditdtim >= @auditstart and auditdtim <= @auditend; 

наличие индексов в основном влияет на производительность запроса, не так, как написано.

Answer 2

Вы должны иметь возможность использовать два бинарных поиска в AuditRowId.

Чтобы найти идентификатор, связанный со временем начала, а другой, чтобы найти идентификатор, связанный с временем окончания, а затем выполнить поиск диапазона между этими двумя идентификаторами.

Пример основной идеи ниже: SQL Fiddle (хотя я не гарантирую, что это ошибка бесплатно)

DECLARE @AuditDTimStart DATETIME = '2000-01-15', 
     @AuditDTimEnd DATETIME = '2000-01-20' 

IF @AuditDTimEnd < @AuditDTimStart 
    RAISERROR('Start date after end date',16,1) 

DECLARE @AuditRowIdStart INT, 
     @AuditRowIdEnd INT, 
     @AuditRowIdMin1 INT, 
     @AuditRowIdMax1 INT, 
     @AuditRowIdMin2 INT, 
     @AuditRowIdMax2 INT 

SELECT TOP 1 @AuditRowIdMin1 = AuditRowId, 
      @AuditRowIdMin2 = AuditRowId, 
      @AuditRowIdStart = -1 + CASE 
             WHEN @AuditDTimStart < AuditDTim 
             THEN AuditRowId 
            END 
FROM YourTable 
ORDER BY AuditRowId 

SELECT TOP 1 @AuditRowIdMax1 = AuditRowId, 
      @AuditRowIdMax2 = AuditRowId, 
      @AuditRowIdEnd = 1 + CASE 
            WHEN @AuditDTimEnd > AuditDTim 
             THEN AuditRowId 
            END 
FROM YourTable 
ORDER BY AuditRowId DESC 

WHILE @AuditRowIdStart IS NULL 
    BEGIN 
     -- Binary search to find latest row where AuditDTim < @AuditDTimStart 
     SELECT TOP 1 @AuditRowIdMax1 = CASE 
             WHEN AuditDTim >= @AuditDTimStart 
             THEN AuditRowId 
             ELSE @AuditRowIdMax1 
            END, 
        @AuditRowIdMin1 = CASE 
             WHEN AuditDTim < @AuditDTimStart 
             THEN AuditRowId 
             ELSE @AuditRowIdMin1 
            END 
     FROM YourTable 
     WHERE AuditRowId <= @AuditRowIdMin1 + ((@AuditRowIdMax1 - @AuditRowIdMin1)/2) 
     ORDER BY AuditRowId DESC 

     IF @AuditRowIdMax1 - @AuditRowIdMin1 <= 1 
     SET @AuditRowIdStart = @AuditRowIdMin1; 
    END 

WHILE @AuditRowIdEnd IS NULL 
    BEGIN 
     -- Binary search to find earliest row where AuditDTim > @AuditRowIdEnd 
     SELECT TOP 1 @AuditRowIdMax2 = CASE 
             WHEN AuditDTim > @AuditDTimEnd 
             THEN AuditRowId 
             ELSE @AuditRowIdMax2 
            END, 
        @AuditRowIdMin2 = CASE 
             WHEN AuditDTim <= @AuditDTimEnd 
             THEN AuditRowId 
             ELSE @AuditRowIdMin2 
            END 
     FROM YourTable 
     WHERE AuditRowId >= @AuditRowIdMin2 + ((@AuditRowIdMax2 - @AuditRowIdMin2)/2) 
     ORDER BY AuditRowId ASC 

     IF @AuditRowIdMax2 - @AuditRowIdMin2 <= 1 
     SET @AuditRowIdEnd = @AuditRowIdMax2; 
    END 

SELECT * 
FROM YourTable 
WHERE AuditRowId > @AuditRowIdStart 
     AND AuditRowId < @AuditRowIdEnd 
ORDER BY AuditRowId 

Answer 3

Вслед за ответ Мартина. Пробовал использовать выражение cte. Добавлено @http://sqlfiddle.com/#!6/0270c/9/0.

Код:

--declare @SearchTerm datetime = '2000-01-11 00:00:00'; 
; with cte as 
(
    select TOP 1 
     Iter=convert(int,0), 
     CurDTim=convert(datetime, null), 
     CurId=convert(int, -1), 
     CurMinId=convert(int,-1), 
     CurMaxId=convert(int,-1), 
     NextMinId=MIN([AuditRowId]), 
     NextMaxId=MAX([AuditRowId]) 
    from [YourTable] (nolock) --assume clustered index only on AuditRowId 
    UNION ALL 
    select 
     Iter=Iter+1, 
     CurDTim=NextDTim, 
     CurId=(((NextMaxId+NextMinId)/2)+1), 
     CurMinId=NextMinId, 
     CurMaxId=NextMaxId, 
     NextMinId=case when NextDTim<(/*@SearchTerm*/ '2000-01-11 00:00:00' /*@SearchTerm*/) then (((NextMaxId+NextMinId)/2)+1) else NextMinId end, 
     NextMaxId=case when NextDTim>(/*@SearchTerm*/ '2000-01-11 00:00:00' /*@SearchTerm*/) then (((NextMaxId+NextMinId)/2)+1) else NextMaxId end 
    from cte t1 
    inner join (select AuditRowId, NextDTim=AuditDTim from [YourTable] (nolock)) as t2 
     on [AuditRowId] = (((NextMaxId+NextMinId)/2)+1) 
    where 
     NextMinId < NextMaxId 
     and (((NextMaxId+NextMinId)/2)+1) > NextMinId 
     and (((NextMaxId+NextMinId)/2)+1) < NextMaxId 
     and (CurDTim <> (/*@SearchTerm*/ '2000-01-11 00:00:00' /*@SearchTerm*/) or CurDTim is null) 
) 
select TOP 100 t1.* 
from cte t1 
order by t1.Iter 
;