Основная проблема (на больших объёмах данных) у авторского запроса в том, что он выполняется за время O(n^2)
, т.к. при обработке каждой записи 1-й таблицы он будет читать вторую таблицу целиком. (здесь и далее, буду считать, что обе таблицы содержат одинаковое число строк, равное n
)
Условия вида WorkStart < ISNULL(StatusStop, @time_now)
особо не помогают - даже если бы такое условие "ходило" по индексу, то в среднем случае читало бы не всю 2-ю таблицу, а её половину - и это всё тот же O(n^2)
.
В данной задаче мало способов уменьшить оценку запроса. Наиболее простой из них: ускорить выборку подходящих записей из 2-й таблицы (мы же знаем, что на самом деле их очень мало). В этом могут помочь такие реализации соединения таблиц, как Hash Join
и Merge Join
. Но чтобы задействовать любое из них, в запросе нужна колонка, по которой будем выполнять условие равенства, по типу такого tbl1.Hash_Column = tbl2.Hash_Column
. И чем меньше записей приходится на каждое отдельное значение данного столбца, тем лучше.
Где возьмём дополнительный столбец? Да просто вычислим в запросе. К требованию селективности вполне подойдёт начальная дата интервала с вырезанным из неё временем.
Теперь, выборка из каждой исходной таблицы может выглядеть примерно так:
Select
Hash_Date = Cast(Time_Begin as date),
Time_Begin, Time_End = IsNull(Time_End, @time_now)
From
(
Select
Time_Begin = TimeChange,
Time_End = Lead(TimeChange) Over (Order By TimeChange),
Status_Begin = [Status],
Status_End = Lead([Status]) Over (Order By TimeChange)
From
dbo.tbl1
) t
Where ( Status_Begin = 1 ) and ( IsNull(Status_End, 1) = 0 )
К сожалению, при таком подходе появляется проблема: что, если интервал начинается в один день, а заканчивается в другой? Да, всё правильно - если во второй таблице соответствующий интервал и начинается, и заканчивается в "другой" день, то мы эту пару интервалов потеряем.
На самом деле проблема решаемая. В описании задачи - учёт рабочего времени, следовательно разница дат в любом случае будет невелика (даже если система учёта засбоила и несколько записей в таблице были утеряны). Так что, можем без особых потерь размножить подобные записи по количеству дней на интервале, и пусть значение Hash_Column
принимает все возможные значения даты из интервала.
Допустим, в 1-й таблице имеется интервал 2020-03-01 22:00
- 2020-03-03 05:10
. В этом случае выборка должна будет содержать 3 записи:
Hash_Column / Time_Start / Time_End
2020-03-01 / 2020-03-01 22:00 / 2020-03-03 05:10
2020-03-02 / 2020-03-01 22:00 / 2020-03-03 05:10
2020-03-03 / 2020-03-01 22:00 / 2020-03-03 05:10
Теперь, с какой бы из 3-х возможных дат ни начинался соответствующий интервал во 2-й таблице, мы сможем поймать их по равенству колонки Hash_Column
.
Остался только один вопрос: что, если в обеих таблицах соответствующие интервалы длятся по нескольку дней, ведь результаты будут множиться (дубли строк)? Ну это, если честно, вообще не проблема - либо махнуть рукой и написать distinct
на результат соединения, либо добавить в соединении дополнительное условие на колонку Hash_Column
- чтобы она попадала либо на начальную дату интервала из 1-й таблицы, либо на начальную дату интервала из 2-й таблицы.
Ну вот, вроде всё учтено, размножим строки с помощью рекурсивного CTE и получим итоговый запрос:
Declare @time_now datetime = getdate();
With
intervals_1 As
(
Select
Hash_Date = Cast(Time_Begin as date),
Time_Begin, Time_End = IsNull(Time_End, @time_now)
From
(
Select
Time_Begin = TimeChange,
Time_End = Lead(TimeChange) Over (Order By TimeChange),
Status_Begin = [Status],
Status_End = Lead([Status]) Over (Order By TimeChange)
From
dbo.tbl1
) t
Where ( Status_Begin = 1 ) and ( IsNull(Status_End, 1) = 0 )
Union All
Select DateAdd(dd, 1, Hash_Date), Time_Begin, Time_End
From intervals_1
Where ( Hash_Date < Cast(Time_End as date) )
),
intervals_2 As
(
Select
Hash_Date = Cast(Time_Begin as date),
Time_Begin, Time_End = IsNull(Time_End, @time_now)
From
(
Select
Time_Begin = TimeChange,
Time_End = Lead(TimeChange) Over (Order By TimeChange),
Status_Begin = [Status],
Status_End = Lead([Status]) Over (Order By TimeChange)
From
dbo.tbl2
) t
Where ( Status_Begin = 1 ) and ( IsNull(Status_End, 1) = 0 )
Union All
Select DateAdd(dd, 1, Hash_Date), Time_Begin, Time_End
From intervals_2
Where ( Hash_Date < Cast(Time_End as date) )
)
Select
TimeStart = IIf(t1.Time_Begin >= t2.Time_Begin, t1.Time_Begin, t2.Time_Begin),
TimeStop = IIf(t1.Time_End <= t2.Time_End, t1.Time_End, t2.Time_End)
From
intervals_1 t1
Inner Hash Join intervals_2 t2 On
( t1.Hash_Date = t2.Hash_Date )
Where
( t1.Time_Begin <= t2.Time_End ) and ( t2.Time_Begin <= t1.Time_End ) and
( t1.Hash_Date In ( Cast(t1.Time_Begin as date), Cast(t2.Time_Begin as date) ) )
Когда в таблицах tbl1
и tbl2
по 1 миллиону строк, данный запрос у меня отрабатывает за 8-10 секунд.
Схему таблиц создал авторским скриптом: http://sqlfiddle.com/#!18/afad9e/2
Для заполнения таблиц тестовыми данными использовал следующий скрипт:
Set NoCount On;
Declare
@rec_count int = 500000,
@i int,
@dt datetime;
Truncate Table dbo.tbl1;
Truncate Table dbo.tbl2;
Set @i = 0;
Set @dt = '20100101 10:00:00';
While ( @i < @rec_count )
Begin
Insert Into dbo.tbl1 ( TimeChange, [Status] )
Values ( @dt, 1 );
Set @dt = dateadd(ss, 360 + 360 * 7 * rand(), @dt);
Insert Into dbo.tbl1 ( TimeChange, [Status] )
Values ( @dt, 0 );
Set @dt = dateadd(ss, 360 * 15 + 360 * 2 * rand(), @dt);
Set @i = @i + 1;
End;
Set @i = 0;
Set @dt = '20100101 10:00:00';
While ( @i < @rec_count )
Begin
Insert Into dbo.tbl2 ( TimeChange, [Status] )
Values ( @dt, 1 );
Set @dt = dateadd(ss, 360 + 360 * 7 * rand(), @dt);
Insert Into dbo.tbl2 ( TimeChange, [Status] )
Values ( @dt, 0 );
Set @dt = dateadd(ss, 360 * 15 + 360 * 2 * rand(), @dt);
Set @i = @i + 1;
End;
LEAD(TimeChange) OVER