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?

Why does your "For example" output exclude the 534 to 543 line? — Frank, Oct 12 '15 at 12:00
@Frank Have you deleted your answer? I thought it included the three lines required anyway? — tospig, Oct 12 '15 at 23:14
Yes, sorry, I thought that it was wrong (as in, would give wrong results in a different case from your example), but looking again, have changed my mind and undeleted. — Frank, Oct 13 '15 at 00:06
We're looking into non-equi joins extensions for data tables. Will update this post once done. — Arun, Feb 08 '16 at 20:45

Frank · Answer 1 · 2015-10-13T00:06:29.087

3

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.

edited Oct 13 '15 at 00:06

answered Oct 12 '15 at 12:03

Frank

66,179
8
96
180

1

I read to quickly and thought you said "here's the clever approach". I thought "no, that's not clever!", and then realized my mistake. Clever or not, it's the only working answer so far :) – Gregor Thomas Oct 13 '15 at 00:14
This method benchmarks quicker than my method. I now need to test how well it scales to my actual data. – tospig Oct 13 '15 at 01:48
playing about with another data.table variation (inspired by this answer) `dt_arrive[dt_depart, nomatch=0, allow.cartesian=TRUE][i.arrival_minutes > arrival_minutes]` seems quicker still. – tospig Oct 18 '15 at 02:09
@tospig I'm curious, what does `nomatch` change here? Have you found that either sort of merge (since yours is also a merge) scales well? Generally, I've found that cross/Cartesian operations (including the `outer` function) bring my computer to a standstill routinely. – Frank Oct 18 '15 at 02:33
I've not attempted this on my actual data yet, and I don't know enough about the guts of data.table to explain what `nomatch` is doing, I just use it whenever I need an inner-join. In the past I've not had any issues with cartesian joins slowing my computer though - but I may not have had enough data to test it.. – tospig Oct 18 '15 at 02:46

tospig · Answer 2 · 2016-02-08T20:58:23.367

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

Inner join using an inequality expression

2 Answers2

Linked