Inner join using an inequality expression

Question

Background

(Not required for the question, but may be useful to read)

Rolling join on data.table with duplicate keys

Odd behaviour when joining with multiple conditions

Data

library(data.table)   ## using version 1.9.6
## arrival timetable
dt_arrive <- structure(list(txn_id = c(1L, 1L, 1L, 1L, 1L), place = c("place_a", 
"place_a", "place_a", "place_a", "place_a"), arrival_minutes = c(515, 
534, 547, 561, 581), journey_id = 1:5), .Names = c("txn_id", 
"place", "arrival_minutes", "journey_id"), class = c("data.table", 
"data.frame"), row.names = c(NA, -5L), sorted = c("txn_id", 
"place"))

## departure timetable
dt_depart <- structure(list(txn_id = c(1L, 1L, 1L, 1L), place = c("place_a", 
"place_a", "place_a", "place_a"), arrival_minutes = c(489, 507, 
519, 543), journey_id = 10:13), .Names = c("txn_id", "place", 
"arrival_minutes", "journey_id"), sorted = c("txn_id", "place"
), class = c("data.table", "data.frame"), row.names = c(NA, -4L
))

> dt_arrive
   txn_id   place arrival_minutes journey_id
1:      1 place_a             515          1
2:      1 place_a             534          2
3:      1 place_a             547          3
4:      1 place_a             561          4
5:      1 place_a             581          5

> dt_depart
   txn_id   place arrival_minutes journey_id
1:      1 place_a             489         10
2:      1 place_a             507         11
3:      1 place_a             519         12
4:      1 place_a             543         13

Question

I would like to join the arrivals to the departures for only those dt_depart$journey_id that occur after dt_arrive$journey_id in terms of arrival_minutes (i.e. an inner join on txn_id & place)

For example, the output I would like is:

   txn_id   place journey_in_id journey_out_id journey_place_arrive journey_place_depart
      1     place_a          1             12                  515                  519
      1     place_a          1             13                  515                  543
      1     place_a          2             13                  534                  543

Attempts

Using the method from the two linked questions I have constructed

setkey(dt_arrive, txn_id, place)
setkey(dt_depart, txn_id, place)

dt_join <- dt_arrive[dt_depart,
            {
              idx = (i.arrival_minutes > arrival_minutes)
              .(journey_in_id = journey_id[idx],
                journey_out_id = i.journey_id,
                journey_place_arrive = arrival_minutes[idx],
                journey_place_depart = i.arrival_minutes
              )
            },
            by=.EACHI]

But this gives everything from dt_depart, so includes NAs in the result - which suggests a 'right join':

   txn_id   place journey_in_id journey_out_id journey_place_arrive journey_place_depart
1:      1  place_a         NA             10                   NA                  489
2:      1  place_a         NA             11                   NA                  507
3:      1  place_a          1             12                  515                  519
4:      1  place_a          1             13                  515                  543
5:      1  place_a          2             13                  534                  543

I've tried using nomatch=0 to force it to 'inner join', but this hasn't worked.

I can use complete.cases to remove the NA rows, but I was wondering if there's a way of doing this within the query itself?

Answer 1

Here's the unclever approach: take the cross/Cartesian join, and then filter.

merge(dt_arrive, dt_depart, allow.cartesian=TRUE)[arrival_minutes.y > arrival_minutes.x]

#    txn_id   place arrival_minutes.x journey_id.x arrival_minutes.y journey_id.y
# 1:      1 place_a               515            1               519           12
# 2:      1 place_a               515            1               543           13
# 3:      1 place_a               534            2               543           13

By taking the Cartesian join, we're liable to eat up a lot of memory.

Answer 2

A potential solution is to use foverlaps by making some arbitrary interval columns

setDT(dt_arrive)
setDT(dt_depart)

dt_arrive[, `:=`(arrival_minutes_copy = arrival_minutes)]
## reorder columns
dt_arrive <- dt_arrive[, .(txn_id, place, journey_id, arrival_minutes, arrival_minutes_copy)]

dt_depart[, `:=`(arrival_minutes_copy = min(arrival_minutes))]
## reorder columns
dt_depart <- dt_depart[, .(txn_id, place, journey_id, arrival_minutes_copy, arrival_minutes)]

setkey(dt_arrive, arrival_minutes, arrival_minutes_copy)
setkey(dt_depart, arrival_minutes_copy, arrival_minutes)

foverlaps(dt_arrive, 
          dt_depart,
          type = "within",
          nomatch=0L)


#      place txn_id journey_id arrival_minutes_copy arrival_minutes i.txn_id i.journey_id i.arrival_minutes i.arrival_minutes_copy
# 1: place_a      1         12                  489             519        1            1               515                    515
# 2: place_a      1         13                  489             543        1            1               515                    515
# 3: place_a      1         13                  489             543        1            2               534                    534

Benchmarking

library(microbenchmark)

fun_foverlap <- function(dt_a, dt_d){
    dt <- foverlaps(dt_a, 
                                    dt_d,
                        type = "within",
                        nomatch=0L)
    return(dt)
}

fun_merge <- function(dt_a, dt_d){
    dt <- merge(dt_a, dt_d, allow.cartesian=TRUE)[arrival_minutes.y > arrival_minutes.x]
    return(dt)
}

fun_nomatch <- function(dt_a, dt_d){
    dt <- dt_a[dt_d, nomatch=0, allow.cartesian=TRUE][i.arrival_minutes > arrival_minutes]
    return(dt)
}

microbenchmark(fun_foverlap(dt_arrive_foverlap, dt_depart_foverlap),
                             fun_merge(dt_arrive_merge, dt_depart_merge),
                             fun_nomatch(dt_arrive_nomatch, dt_depart_nomatch))

# Unit: microseconds
                                                  expr      min       lq      mean   median        uq      max neval cld
 # fun_foverlap(dt_arrive_foverlap, dt_depart_foverlap) 3538.189 3717.077 3967.6648 3872.586 4006.7205 5812.355   100   c
 #          fun_merge(dt_arrive_merge, dt_depart_merge)  883.697  925.655  980.4159  942.877  967.9745 2223.147   100  b 
 #    fun_nomatch(dt_arrive_nomatch, dt_depart_nomatch)  593.082  625.471  682.8975  643.034  665.4125 2077.748   100 a