0

Есть две таблицы с началом и концом временных промежутков. Необходимо определить время, которое было между этими временными интервалами - например, 10 - 16 и 9 - 15 => 10 - 15. Я решил данную задачу через декартово произведение, однако уверен, что это решение можно улучшить В примере таблица tbl1 отображает статусы сотрудника (где B - рабочий статус), а таблица tbl2 - рабочее и нерабочее время сотрудника (где Work - рабочий статус). NULL же означает, что временной интервал ещё не закрыт и все ещё продолжается.

UPD: Таблицы изначально имели только статус и время изменения, в такой вид я их привел с помощью LEAD(TimeChange) OVER (ORDER BY TimeChange)

DECLARE @time_now time = CAST(GETDATE() AS time)
;WITH tbl1 AS 
(
    SELECT *
    FROM (VALUES 
        ('A', '00:04:05', '00:09:05'),
        ('B', '00:09:05', '00:30:02'),
        ('A', '00:30:02', '04:02:22'),
        ('B', '04:02:22', NULL)
    ) X(Status, StatusStart, StatusStop)
),
tbl2 AS 
(
    SELECT *
    FROM (VALUES
        ('Work', '00:00:00', '00:22:02'),
        ('NoWork', '00:22:02', '05:02:22'),
        ('Work', '05:02:22', NULL)
    ) X(Work, WorkStart, WorkStop)
)

SELECT *
FROM 
(
    SELECT *, 
        IIF(WorkStart > StatusStart, WorkStart, StatusStart) AS TimeStart,
        ISNULL(IIF(WorkStop < StatusStop, WorkStop, StatusStop), @time_now) AS TimeStop
    FROM tbl1, tbl2
    WHERE tbl1.[Status] = 'B' 
        AND tbl2.[Work] = 'Work' 
        AND WorkStart < ISNULL(StatusStop, @time_now) 
        AND ISNULL(WorkStop, @time_now) > StatusStart
) t1
12
  • Я решил данную задачу через декартово произведение Ничто не мешает превратить его в честный JOIN, если часть условий, логически отвечающих за связывание (да хоть все! хотя как по мне - то два последних) переместить из WHERE в ON. уверен, что это решение можно улучшить А существует ли реальная необходимость в улучшении (не синтаксическом, которое описано выше)?
    – Akina
    2 фев 2021 в 7:05
  • Повлияет ли JOIN на производительность? У меня довольно большие таблицы tbl1 и tbl2, там сотни тысяч строк и улучшение поможет снизить нагрузку на сервер. В итоге мне нужно просто количество минут TimeStop - TimeStart 2 фев 2021 в 7:19
  • 1
    Повлияет ли JOIN на производительность? 99% за то, что план не изменится ни на байт. У меня довольно большие таблицы tbl1 и tbl2, там сотни тысяч строк и улучшение поможет снизить нагрузку на сервер. Э/ту проблему надо решать правильным индексированием. Чему ну очень помешает наличие NULL и соответственно необходимость использования функций при связывании. Возможно, если количество записей с NULL не очень велико, имеет смысл отдельно обработать записи с NULL и без, а потом UNION ALL/
    – Akina
    2 фев 2021 в 7:24
  • Я до этого преобразую данные, у меня в самом начале таблица без NULL, но и без окончания интервала, то есть просто TimeChange и статус. К такому виду я её привожу через LEAD(TimeChange) OVER 2 фев 2021 в 7:31
  • 1
    так пробовали? 4 фев 2021 в 15:27

1 ответ 1

2
+150

Основная проблема (на больших объёмах данных) у авторского запроса в том, что он выполняется за время 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;
6
  • Понял - идея в том, чтобы соединять даты, а не размытые условия сравнения datetime 7 фев 2021 в 5:53
  • 1
    Да, именно так. Соединяем по равенству дат, затем "шлифуем" полной версией условия на пересечение диапазонов. Что насчёт быстродействия запроса, устраивает оно в данном варианте? В принципе, тут ещё можно переписать парой курсоров, с которыми на индексах будет честный O(n), но у меня это отрабатывает немного дольше цельного запроса. Наверное, для преимущества в производительности на курсоре должны быть объёмы данных на порядки больше миллиона строк.
    – velial
    7 фев 2021 в 10:18
  • Забавно получилось) Я переписал код на свои реалии, где я внутри каждой таблицы произвожу фильтрацию, так вот, при INNER JOIN я получаю план выполнения с HASH INNER JOIN и двумя NONCLUSTERED INDEX SEEK, но когда я добавляю хинт INNER HASH JOIN - получаю два INDEX SCAN 13 фев 2021 в 7:01
  • Действительно, забавненько вышло... У меня, на тестовых таблицах, такого эффекта не было: что с хинтом HASH, что без него - план был одинаковым (конечно, на достаточно больших объёмах данных). Наверное, на "боевых" таблицах у Вас есть ещё какие-то столбцы и индексы с их участием. А что по быстродействию обоих вариантов?
    – velial
    13 фев 2021 в 10:16
  • Без хинта - меньше 3-х секунд. С хинтом - больше 2-х минут. Причем без хинта план и так идет с HASH JOIN. Как вариант - темповые таблицы можно 15 фев 2021 в 9:53

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.