Slowdown with `mult = "last"` and non-equi joins

Reproduce the benchmark in the issue, then inspect src/uniqlist.c around the cited nestedid() locations at lines 294 and 330. Confirm the group-count difference for mult = "first" and "last"; done means the last case no longer generates excessive nested groups or shows the reported slowdown.

Hi data table team,

I'd like to report a slowdown related to non-equi joins, in particular when they are combined with mult = "last". Here is an example:

library(data.table)

set.seed(1L)
ids = paste0("id", 1:30e3)
N = 40e3L

query = data.table(id=sample(ids, N, TRUE), range1=sample(1e2L, N, TRUE))
query[, range2 := range1 + as.integer(runif(N)*300L)]
query
#>             id range1 range2
#>     1: id17401     67    149
#>     2: id24388     64    338
#>     3:  id4775     95    249
#>     4: id26753     14    302
#>     5: id13218     31    275
#>    ---                      
#> 39996:     id6      5    119
#> 39997: id18131     73    312
#> 39998:  id8203     23    313
#> 39999: id24941     91    229
#> 40000:  id1999     28    245

subject = data.table(id=sample(ids), range1=sample(2e2L, 30e3L, TRUE))
subject[, range2 := range1 + as.integer(runif(30e3L)*10e3L)]
subject
#>             id range1 range2
#>     1:  id1395    102    482
#>     2:  id9342    108   7416
#>     3:  id8444     72   4170
#>     4:  id9075     88   2419
#>     5: id16817     23   3371
#>    ---                      
#> 29996: id29583    185    439
#> 29997: id26801    177   8087
#> 29998: id21451    172   1521
#> 29999: id17005    136    851
#> 30000: id20003    140    527

bench::mark(
  all   = query[subject, on=.(id, range1>=range1, range2<=range2)],
  first = query[subject, on=.(id, range1>=range1, range2<=range2), mult = "first"],
  last  = query[subject, on=.(id, range1>=range1, range2<=range2), mult = "last"],
  check = FALSE
)
#> # A tibble: 3 x 6
#>   expression      min   median `itr/sec` mem_alloc `gc/sec`
#>   <bch:expr> <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl>
#> 1 all          29.3ms   31.5ms     30.4     4.05MB     2.03
#> 2 first        25.6ms   27.7ms     35.6     2.33MB     0   
#> 3 last        137.9ms  139.5ms      7.16    2.33MB     2.39

"last" is much slower here. The slowdown has to do with the nested group id generation in nestedid().

Right here you either set starts to the start of each group, or, in the case of "last", the end of each group (i.e. 1 less than the next group start).
https://github.com/Rdatatable/data.table/blob/feebb0e3700e0a38d53588ce420071c480170c51/src/uniqlist.c#L294

The problem comes in later on when you check rlen != start here.
https://github.com/Rdatatable/data.table/blob/feebb0e3700e0a38d53588ce420071c480170c51/src/uniqlist.c#L330

rlen is a group start location (coming from the group sizes in resetvals), not a group end location. When rlen == start, this normally results in a nice optimization where the nested group counter starts over, but since you are comparing a group start with a group end, that branch rarely runs and you end up with an overly large number of nested groups.

For some proof, here we run with verbose = TRUE and you can see that it generates 1806 groups VS 8 groups for the "first" case.

xx <- query[subject, on=.(id, range1>=range1, range2<=range2), mult = "first", verbose = TRUE]
#> i.id has same type (character) as x.id. No coercion needed.
#> i.range1 has same type (integer) as x.range1. No coercion needed.
#> i.range2 has same type (integer) as x.range2. No coercion needed.
#> Non-equi join operators detected ... 
#>   forder took ... forder.c received 40000 rows and 3 columns
#> 0.009s elapsed (0.009s cpu) 
#>   Generating group lengths ... forder.c received 40000 rows and 3 columns
#> done in 0.008s elapsed (0.007s cpu)
#>   Generating non-equi group ids ... done in 0.001s elapsed (0.001s cpu)
#>   Recomputing forder with non-equi ids ... Assigning to all 40000 rows
#> RHS_list_of_columns == false
#> RHS for item 1 has been duplicated because NAMED==3 MAYBE_SHARED==1, but then is being plonked. length(values)==40000; length(cols)==1)
#> forder.c received 40000 rows and 4 columns
#> done in 0.007s elapsed (0.006s cpu)
#>   Found 8 non-equi group(s) ...
#> Starting bmerge ...
#> forder.c received 30000 rows and 3 columns
#> bmerge done in 0.015s elapsed (0.015s cpu)

xx <- query[subject, on=.(id, range1>=range1, range2<=range2), mult = "last", verbose = TRUE]
#> i.id has same type (character) as x.id. No coercion needed.
#> i.range1 has same type (integer) as x.range1. No coercion needed.
#> i.range2 has same type (integer) as x.range2. No coercion needed.
#> Non-equi join operators detected ... 
#>   forder took ... forder.c received 40000 rows and 3 columns
#> 0.008s elapsed (0.008s cpu) 
#>   Generating group lengths ... forder.c received 40000 rows and 3 columns
#> done in 0.007s elapsed (0.007s cpu)
#>   Generating non-equi group ids ... done in 0.102s elapsed (0.102s cpu)
#>   Recomputing forder with non-equi ids ... Assigning to all 40000 rows
#> RHS_list_of_columns == false
#> RHS for item 1 has been duplicated because NAMED==3 MAYBE_SHARED==1, but then is being plonked. length(values)==40000; length(cols)==1)
#> forder.c received 40000 rows and 4 columns
#> done in 0.006s elapsed (0.006s cpu)
#>   Found 1806 non-equi group(s) ...
#> Starting bmerge ...
#> forder.c received 30000 rows and 3 columns
#> bmerge done in 0.035s elapsed (0.034s cpu)

I think you need to track the true group start location alongside starts and use that in the comparison against rlen, so that even when "last" is used you are comparing a group start against a group start.