A rolling join refers to a situation in which two or more tables need to be associated, but there isn’t a direct correspondence of values in each table’s key column(s). For example, assume we have a table that represents thresholds in which to group claims based on loss amount:
library("data.table")
DF1 = data.table(
group=c("A", "B", "C", "D", "E"),
loss=c(0, 10000, 20000, 30000, 40000),
stringsAsFactors=FALSE
)Reviewing the contents of DF1:
group loss
1: A 0
2: B 10000
3: C 20000
4: D 30000
5: E 40000Let’s also assume we have a table of claims, DF2:
DF2 = data.table(
claimno=paste0("000", 10:20),
loss=c(8101, 15700, 64140, 20000, 11655, 31850, 23680, 41440, 16161, 77000, 4564),
stringsAsFactors=FALSE
)Reviewing the contents of DF2:
claimno loss
1: 00010 8101
2: 00011 15700
3: 00012 64140
4: 00013 20000
5: 00014 11655
6: 00015 31850
7: 00016 23680
8: 00017 41440
9: 00018 16161
10: 00019 77009
11: 00020 4564The goal is for each claimno in DF2, assign the corresponding group from DF1 such that loss threshold (from DF1) is the maximum value less than or equal to loss from DF2. For example, a loss amount of 15700 should be assigned to group B, since 10000 is the maximum loss threshold less than or equal to 15700.
The way many people first attack this problem is to use a deeply nested sequence of ifelse statements. Something akin to:
DF2[,
group:=
ifelse(loss>=0 & loss<10000, "A",
ifelse(loss>=10000 & loss<20000, "B",
ifelse(loss>=20000 & loss<30000, "C",
ifelse(loss>=30000 & loss<40000, "D",
"E"
)
)
)
)
]Which results in:
claimno loss group
1: 00010 8101 A
2: 00011 15700 B
3: 00012 64140 E
4: 00013 20000 C
5: 00014 11655 B
6: 00015 31850 D
7: 00016 23680 C
8: 00017 41440 E
9: 00018 16161 B
10: 00019 77000 E
11: 00020 4564 AThis solution works, but is not optimal for a number of reasons. First, it’s overly verbose and brittle. If the number of groups changes from 5 to 10 or 15, it becomes necessary to extend the nesting of ifelses by the number of new groups. One should always try to avoid writing code that requires updates in proportion to the size of the input. Perhaps more importantly, this approach has poor runtime performance, which we demonstrate later on.
Rolling Joins
Performing a rolling join in data.table is straightforward. Simply add the roll modifier within the join expression, specifying either +Inf (or TRUE) or -Inf to specify the direction in which to roll. Sticking with the same DF1 and DF2 from before, we create a new table DF, which represents DF2 along with the target group associated with each claimno:
DF = DF1[DF2, on="loss", roll=+Inf]Resulting in:
group loss claimno
1: A 8101 00010
2: B 15700 00011
3: E 64140 00012
4: C 20000 00013
5: B 11655 00014
6: D 31850 00015
7: C 23680 00016
8: E 41440 00017
9: B 16161 00018
10: E 77000 00019
11: A 4564 00020Note that in this example, the key column loss is the same in both tables. If this was not the case, say, threshold in DF1 vs. loss in DF2, one would specify on=c("threshold"="loss").
For completeness, let’s see what happens if switch to roll=-Inf (assume we changed loss to threshold in DF1):
DF = DF1[DF2, on=c("threshold"="loss"), roll=-Inf]Resulting in:
group threshold claimno
1: B 8101 00010
2: C 15700 00011
3: <NA> 64140 00012
4: C 20000 00013
5: C 11655 00014
6: E 31850 00015
7: D 23680 00016
8: <NA> 41440 00017
9: C 16161 00018
10: <NA> 77000 00019
11: B 4564 00020Any value in excess of the largest threshold gets set to NA, and all other claims get set to the minimum threshold from DF1 greater than or equal to loss in DF1.
Performance Comparison
To demonstrate to difference in performance, we generate a new DF2 with one million random claim amounts. We’ll then compare the performance between the naive initial implementation and the rolling join implementation. To make it easier to use with the microbenchmark profiling tool, each implementation is encapsulated within separate functions:
library("data.table")
library("microbenchmark")
DF1 = data.table(
group=c("A", "B", "C", "D", "E"),
loss=c(0, 10000, 20000, 30000, 40000),
stringsAsFactors=FALSE
)
DF2 = data.table(
claimno=formatC(1:1000000, format="d", width=7, flag=0),
loss=rgamma(n=1000000, shape=1, scale=25000),
stringsAsFactors=FALSE
)
# Create copies to operate on for each implementation.
method1DF = data.table::copy(DF2)
method2DF = data.table::copy(DF2)
fmethod1 = function() {
# First method.
method1DF[,
group:=
ifelse(loss>=0 & loss<10000, "A",
ifelse(loss>=10000 & loss<20000, "B",
ifelse(loss>=20000 & loss<30000, "C",
ifelse(loss>=30000 & loss<40000, "D",
"E"
)
)
)
)
]
}
fmethod2 = function() {
# Second method.
DF = DF1[method2DF, on=c("loss"), roll=+Inf]
}
# Run comparison 10 times, compare max result from each.
microbenchmark(
fmethod1(),
fmethod2(),
times=10
)The results from microbenchmark are provided below:
Unit: milliseconds
expr min lq mean median uq max neval
fmethod1() 2116.3529 2212.5053 2518.0355 2558.7205 2779.6253 3061.8588 10
fmethod2() 494.8094 536.9963 622.7095 586.1551 677.1586 825.6939 10In the worst case, the rolling join approach is almost 4 times faster, and as the number of records increases, so does the relative performance improvement between the two methods.