Соединение по периоду времени

  • Статья

Часто бывает полезно объединить два больших набора данных в некоторых ключах с высокой кратностью, например идентификатор операции или идентификатор сеанса, и дополнительно ограничить правосторонние ($right) записи, которые должны сопоставляться с каждой левой записью ($left), добавив ограничение на "расстояние по времени" между datetime столбцами слева и справа.

Приведенная выше операция отличается от обычной операции соединения Kusto, так как для equi-join части сопоставления ключа с высокой кратностью между левым и правым наборами данных система также может применить функцию расстояния и использовать ее для значительного ускорения соединения.

Примечание

Функция distance не ведет себя как равенство (то есть, если и dist(x,y) и dist(y,z) являются истинными, это не следует за тем, что dist(x,z) также верно.) Внутри мы иногда называем это "диагональным соединением".

Например, если вы хотите определить последовательности событий в течение относительно небольшого временного периода, предположим, что у вас есть таблица T со следующей схемой:

  • SessionId: столбец типа string с идентификаторами корреляции.
  • EventType: столбец типа string , определяющий тип события записи.
  • Timestamp: столбец типа datetime указывает, когда произошло событие, описанное в записи.

Выполнить запрос

let T = datatable(SessionId:string, EventType:string, Timestamp:datetime)
[
    '0', 'A', datetime(2017-10-01 00:00:00),
    '0', 'B', datetime(2017-10-01 00:01:00),
    '1', 'B', datetime(2017-10-01 00:02:00),
    '1', 'A', datetime(2017-10-01 00:03:00),
    '3', 'A', datetime(2017-10-01 00:04:00),
    '3', 'B', datetime(2017-10-01 00:10:00),
];
T

Выходные данные

SessionId EventType Отметка времени
0 A 2017-10-01 00:00:00.0000000
0 B 2017-10-01 00:01:00.0000000
1 B 2017-10-01 00:02:00.0000000
1 A 2017-10-01 00:03:00.0000000
3 A 2017-10-01 00:04:00.0000000
3 B 2017-10-01 00:10:00.0000000

Оператор задачи

Наш запрос должен ответить на следующий вопрос:

Найдите все идентификаторы сеансов, за которыми следует тип AB события в течение определенного 1min периода времени.

Примечание

В приведенном выше примере данных единственным идентификатором сеанса является 0.

Семантически следующий запрос отвечает на этот вопрос, хотя и неэффективно.

Выполнить запрос

T 
| where EventType == 'A'
| project SessionId, Start=Timestamp
| join kind=inner
    (
    T 
    | where EventType == 'B'
    | project SessionId, End=Timestamp
    ) on SessionId
| where (End - Start) between (0min .. 1min)
| project SessionId, Start, End

Выходные данные

SessionId Начать Конец
0 2017-10-01 00:00:00.0000000 2017-10-01 00:01:00.0000000

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

Перепишите запрос с учетом временного окна.

Перепишите запрос так, чтобы datetime значения были "дискретизированы" в контейнеры, размер которых составляет половину размера временного окна. Используйте kusto equi-join для сравнения этих идентификаторов контейнеров.

let lookupWindow = 1min;
let lookupBin = lookupWindow / 2.0; // lookup bin = equal to 1/2 of the lookup window
T 
| where EventType == 'A'
| project SessionId, Start=Timestamp,
          // TimeKey on the left side of the join is mapped to a discrete time axis for the join purpose
          TimeKey = bin(Timestamp, lookupBin)
| join kind=inner
    (
    T 
    | where EventType == 'B'
    | project SessionId, End=Timestamp,
              // TimeKey on the right side of the join - emulates event 'B' appearing several times
              // as if it was 'replicated'
              TimeKey = range(bin(Timestamp-lookupWindow, lookupBin),
                              bin(Timestamp, lookupBin),
                              lookupBin)
    // 'mv-expand' translates the TimeKey array range into a column
    | mv-expand TimeKey to typeof(datetime)
    ) on SessionId, TimeKey 
| where (End - Start) between (0min .. lookupWindow)
| project SessionId, Start, End

Справочник по выполняемым запросам (со встроенной таблицей)

Выполнить запрос

let T = datatable(SessionId:string, EventType:string, Timestamp:datetime)
[
    '0', 'A', datetime(2017-10-01 00:00:00),
    '0', 'B', datetime(2017-10-01 00:01:00),
    '1', 'B', datetime(2017-10-01 00:02:00),
    '1', 'A', datetime(2017-10-01 00:03:00),
    '3', 'A', datetime(2017-10-01 00:04:00),
    '3', 'B', datetime(2017-10-01 00:10:00),
];
let lookupWindow = 1min;
let lookupBin = lookupWindow / 2.0;
T 
| where EventType == 'A'
| project SessionId, Start=Timestamp, TimeKey = bin(Timestamp, lookupBin)
| join kind=inner
    (
    T 
    | where EventType == 'B'
    | project SessionId, End=Timestamp,
              TimeKey = range(bin(Timestamp-lookupWindow, lookupBin),
                              bin(Timestamp, lookupBin),
                              lookupBin)
    | mv-expand TimeKey to typeof(datetime)
    ) on SessionId, TimeKey 
| where (End - Start) between (0min .. lookupWindow)
| project SessionId, Start, End

Выходные данные

SessionId Начать Конец
0 2017-10-01 00:00:00.0000000 2017-10-01 00:01:00.0000000

5 млн. запрос данных

Следующий запрос эмулирует набор данных из 5 млн записей и около 1 млн идентификаторов и выполняет запрос с помощью описанной выше методики.

Выполнить запрос

let T = range x from 1 to 5000000 step 1
| extend SessionId = rand(1000000), EventType = rand(3), Time=datetime(2017-01-01)+(x * 10ms)
| extend EventType = case(EventType < 1, "A",
                          EventType < 2, "B",
                          "C");
let lookupWindow = 1min;
let lookupBin = lookupWindow / 2.0;
T 
| where EventType == 'A'
| project SessionId, Start=Time, TimeKey = bin(Time, lookupBin)
| join kind=inner
    (
    T 
    | where EventType == 'B'
    | project SessionId, End=Time, 
              TimeKey = range(bin(Time-lookupWindow, lookupBin), 
                              bin(Time, lookupBin),
                              lookupBin)
    | mv-expand TimeKey to typeof(datetime)
    ) on SessionId, TimeKey 
| where (End - Start) between (0min .. lookupWindow)
| project SessionId, Start, End 
| count

Выходные данные

Count
3344