Tidsfönsterkoppling

Det är ofta användbart att koppla mellan två stora datauppsättningar på en nyckel med hög kardinalitet, till exempel ett åtgärds-ID eller ett sessions-ID, och ytterligare begränsa de poster på höger sida ($right) som måste matchas med varje post på vänster sida ($left) genom att lägga till en begränsning på "tidsavståndet" mellan datetime kolumner till vänster och till höger.

Ovanstående åtgärd skiljer sig från den vanliga Kusto-kopplingsåtgärden, eftersom systemet för den equi-join del av matchningen av nyckeln med hög kardinalitet mellan de vänstra och högra datauppsättningarna också kan tillämpa en avståndsfunktion och använda den för att avsevärt påskynda kopplingen.

Anteckning

En avståndsfunktion beter sig inte som likhet (dvs. när både dist(x,y) och dist(y,z) är sanna följer den inte att dist(x,z) också är sant.) Internt kallar vi ibland detta för "diagonal koppling".

Om du till exempel vill identifiera händelsesekvenser inom ett relativt litet tidsfönster antar du att du har en tabell T med följande schema:

  • SessionId: En kolumn av typen string med korrelations-ID:t.
  • EventType: En kolumn av typen string som identifierar postens händelsetyp.
  • Timestamp: En kolumn av typen datetime anger när händelsen som beskrivs av posten inträffade.
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

Resultat

Sessionid Eventtype 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

Problembeskrivning

Vår fråga bör besvara följande fråga:

Hitta alla sessions-ID:t där händelsetypen A följdes av en händelsetyp B inom ett 1min tidsfönster.

Anteckning

I exempeldata ovan är 0det enda sådana sessions-ID:t .

Semantiskt svarar följande fråga på den här frågan, om än ineffektivt.

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 

Resultat

Sessionid Start Slut
0 2017-10-01 00:00:00.0000000 2017-10-01 00:01:00.0000000

För att optimera den här frågan kan vi skriva om den enligt beskrivningen nedan så att tidsfönstret uttrycks som en kopplingsnyckel.

Skriv om frågan för att ta hänsyn till tidsfönstret

Skriv om frågan så att datetime värdena "diskretiseras" till bucketar vars storlek är hälften så stor som tidsfönstret. Använd Kusto för equi-join att jämföra dessa bucket-ID:n.

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 

Körbar frågereferens (med inlindad tabell)

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 

Resultat

Sessionid Start Slut
0 2017-10-01 00:00:00.0000000 2017-10-01 00:01:00.0000000

5M-datafråga

Nästa fråga emulerar en datauppsättning med 5M-poster och ~1M-ID:n och kör frågan med den teknik som beskrivs ovan.

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 

Resultat

Antal
3344