Partager via

Jointure de fenêtre de temps

  • Article

Il est souvent utile de joindre deux jeux de données volumineux sur une clé à cardinalité élevée, comme un ID d’opération ou un ID de session, et de limiter davantage les enregistrements de droite ($right) qui doivent correspondre à chaque enregistrement de gauche ($left) en ajoutant une restriction sur la « distance temporelle » entre datetime les colonnes à gauche et à droite.

L’opération ci-dessus diffère de l’opération de jointure Kusto habituelle, car pour la equi-join partie de la correspondance de la clé de cardinalité élevée entre les jeux de données de gauche et de droite, le système peut également appliquer une fonction de distance et l’utiliser pour accélérer considérablement la jointure.

Notes

Une fonction de distance ne se comporte pas comme une égalité (autrement dit, lorsque dist(x,y) et dist(y,z) sont true, il ne suit pas que dist(x,z) est également true.) En interne, nous l’appelons parfois « jointure diagonale ».

Par exemple, si vous souhaitez identifier des séquences d’événements dans une fenêtre de temps relativement petite, supposons que vous disposez d’une table T avec le schéma suivant :

  • SessionId: colonne de type string avec des ID de corrélation.
  • EventType: colonne de type string qui identifie le type d’événement de l’enregistrement.
  • Timestamp: une colonne de type datetime indique quand l’événement décrit par l’enregistrement s’est produit.

Exécuter la requête

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

Sortie

SessionId Type d’événement Timestamp
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

Définition du problème

Notre requête doit répondre à la question suivante :

Recherchez tous les ID de session dans lesquels le type A d’événement a été suivi d’un type B d’événement dans une 1min fenêtre de temps.

Notes

Dans les exemples de données ci-dessus, le seul ID de session de ce type est 0.

Sémantiquement, la requête suivante répond à cette question, bien que de manière inefficace.

Exécuter la requête

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

Sortie

SessionId Démarrer End
0 2017-10-01 00:00:00.0000000 2017-10-01 00:01:00.0000000

Pour optimiser cette requête, nous pouvons la réécrire comme décrit ci-dessous afin que la fenêtre de temps soit exprimée sous forme de clé de jointure.

Réécrire la requête pour tenir compte de la fenêtre de temps

Réécrire la requête afin que les datetime valeurs soient « discrétisées » dans des compartiments dont la taille est la moitié de la taille de la fenêtre de temps. Utilisez Kusto equi-join pour comparer ces ID de compartiment.

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

Référence de requête exécutable (avec table insérée)

Exécuter la requête

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

Sortie

SessionId Démarrer End
0 2017-10-01 00:00:00.0000000 2017-10-01 00:01:00.0000000

Requête de données de 5 millions

La requête suivante émule un jeu de données de 5 millions d’enregistrements et environ 1 millions d’ID et exécute la requête avec la technique décrite ci-dessus.

Exécuter la requête

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

Sortie

Count
3344