Time window-join

Het is vaak handig om twee grote gegevenssets samen te voegen op een sleutel met een hoge kardinaliteit, zoals een bewerkings-id of een sessie-id, en de records aan de rechterkant ($right) verder te beperken die moeten overeenkomen met elke record aan de linkerkant ($left) door een beperking toe te voegen op de 'tijdafstand' tussen datetime kolommen links en rechts.

De bovenstaande bewerking wijkt af van de gebruikelijke Kusto-joinbewerking, omdat het systeem voor het koppelen van de equi-join sleutel met hoge kardinaliteit tussen de linker- en rechtergegevenssets ook een afstandsfunctie kan toepassen en deze kan gebruiken om de join aanzienlijk te versnellen.

Notitie

Een afstandsfunctie gedraagt zich niet als gelijkheid (dat wil gezegd, wanneer zowel dist(x,y) als dist(y,z) waar zijn, betekent dit niet dat dist(x,z) ook waar is.) Intern noemen we dit soms 'diagonal join'.

Als u bijvoorbeeld gebeurtenissenreeksen binnen een relatief klein tijdvenster wilt identificeren, wordt ervan uitgegaan dat u een tabel T met het volgende schema hebt:

• SessionId: Een kolom van het type string met correlatie-id's.
• EventType: Een kolom van het type string die het gebeurtenistype van de record identificeert.
• Timestamp: Een kolom van het type datetime geeft aan wanneer de gebeurtenis die door de record wordt beschreven, heeft plaatsgevonden.

De query uitvoeren

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

Uitvoer

Sessionid	EventType	Tijdstempel
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

Probleemformulering

Onze query moet de volgende vraag beantwoorden:

Zoek alle sessie-id's waarin het gebeurtenistype A is gevolgd door een gebeurtenistype B binnen een 1min tijdvenster.

Notitie

In de bovenstaande voorbeeldgegevens is 0de enige sessie-id .

Semantisch gezien beantwoordt de volgende query deze vraag, zij het ineen efficiënt.

De query uitvoeren

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 

Uitvoer

Sessionid	Starten	Beëindigen
0	2017-10-01 00:00:00.0000000	2017-10-01 00:01:00.0000000

Om deze query te optimaliseren, kunnen we deze herschrijven zoals hieronder wordt beschreven, zodat het tijdvenster wordt uitgedrukt als een joinsleutel.

De query herschrijven om rekening te houden met het tijdvenster

Herschrijf de query zodat de datetime waarden worden 'gedisretiseerd' in buckets waarvan de grootte de helft van het tijdvenster is. Gebruik Kusto's om deze bucket-id's equi-join te vergelijken.

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 

Naslaginformatie over uitvoerbare query's (met tabel inline)

De query uitvoeren

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 

Uitvoer

Sessionid	Starten	Beëindigen
0	2017-10-01 00:00:00.0000000	2017-10-01 00:01:00.0000000

5 miljoen gegevensquery

Met de volgende query wordt een gegevensset met 5M-records en ~1 miljoen id's geëmuleerd en wordt de query uitgevoerd met de hierboven beschreven techniek.

De query uitvoeren

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 

Uitvoer

Count
3344