"notjoin" joins are slow

Open
#2,567 5 comments 0 reactions 1 assignee View on GitHub

@MarkusBonsch is already working on this.

Since Apr 14, 2018.

Assessment

This issue has not been assessed yet.

Description

enhancement joins performance

Usually, joins using bmerge are expected to be faster than vector-based subsets. Therefore, normal subsets are replaced internally by joins for optimization. It turns out, however, that "notjoin" queries are slower as a join than as a simple subset. The reason is the expensive line:

i = irows = if (length(irows)) seq_len(nrow(x))[-irows] else NULL  # NULL meaning all rows i.e. seq_len(nrow(x))

where a long vector is created via seq_len(nrow(x)):

## notjoin issue
## I added verbose messages for finding the issue
DT <- data.table(x = sample(1L:10L, 1e7L, replace = TRUE))

## switch off optimization. Otherwise, simple subset would be translated into a join
options(datatable.use.index = FALSE)

identical(DT[!x == 3L], DT[!data.table(x = 3L), on = "x"])
# [1] TRUE

system.time(DT[!x == 3L, verbose = TRUE])
# user  system elapsed 
# 0.020   0.000   0.018 
system.time(DT[!data.table(x = 3L), on = "x", verbose = TRUE])
# Calculated ad hoc index in 0.06 secs
# Starting bmerge ...done in 0 secs
# Inverting irows for notjoin done in ... 0.23 sec
# user  system elapsed 
# 0.340   0.072   0.412 

# Even with a proper key, the join is not faster
setkey(DT, x)
system.time(DT[!x == 3L, verbose = TRUE])
# user  system elapsed 
# 0.276   0.020   0.297 
system.time(DT[!data.table(x = 3L, key = "x"), verbose = TRUE])
# Starting bmerge ...done in 0.001 secs
# Inverting irows for notjoin done in ... 0.216 sec
# user  system elapsed 
# 0.284   0.060   0.342

Therefore, it doesn't make sense to "optimize" notjoin queries towards bmerge until a fast implementation for the != operator exists in bmerge.

Dominant language
R
Stars
3.9k
Forks
1.1k
Avg merge
14h 4m
Merged PRs (30d)
4

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from Rdatatable/data.table

All issues in Rdatatable/data.table

Similar issues

More R issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.