Repository navigation
binary search on selective keys in CJ() #797
Description
A question related to CJ() (likely also to J()) function used in binary search. I would like to perform CJ() on selective keys. It is currently possible via workaround which requires extra unique() per column. See below:
library(data.table)
product <- data.table(prod_code = 1:16)
customer <- data.table(cust_code = 1:24)
geography <- data.table(state_code = state.abb)
time <- data.table(date_code = seq(as.Date(paste0(year(Sys.Date())-1,"-01-01")),
as.Date(paste0(year(Sys.Date()),"-12-31")),
by = "1 day"))
n <- 1e5
set.seed(2345)
sales <-
data.table(prod_code = sample(product[,prod_code], n, TRUE),
cust_code = sample(customer[,cust_code], n, TRUE),
state_code = sample(geography[,state_code], n, TRUE),
date_code = sample(time[,date_code], n, TRUE),
quantity = rnorm(n, 500, 200),
value = rnorm(n, 10000,2000))
setkeyv(sales,c("prod_code","cust_code","state_code","date_code"))
# binary search filtering works fine on all four keys
sales[CJ(c(12,13,15), c(15,16,21,24),c("TX","AK","CA"),as.Date(c("2013-01-18","2013-01-31","2014-08-06"))), nomatch=0]
# but if I want to binary search on 3 keys, excluding `state_code` I would like to use some kind of:
sales[CJ(c(12,13,15), c(15,16,21,24), , as.Date(c("2013-01-18","2013-01-31","2014-08-06"))), nomatch=0]
sales[CJ(c(12,13,15), c(15,16,21,24), TRUE, as.Date(c("2013-01-18","2013-01-31","2014-08-06"))), nomatch=0]
sales[CJ(c(12,13,15), c(15,16,21,24), NA, as.Date(c("2013-01-18","2013-01-31","2014-08-06"))), nomatch=0]
sales[CJ(c(12,13,15), c(15,16,21,24), character(), as.Date(c("2013-01-18","2013-01-31","2014-08-06"))), nomatch=0]
# none of them works
# binary search workaround, not very nice cause requires `unique`:
sales[CJ(c(12,13,15), c(15,16,21,24), unique(sales[,state_code]), as.Date(c("2013-01-18","2013-01-31","2014-08-06"))), nomatch=0]
# non binary search workaround (used for validation):
sales[CJ(c(12,13,15), c(15,16,21,24)), nomatch=0][date_code %in% as.Date(c("2013-01-18","2013-01-31","2014-08-06"))]Subsetting kind of dt[CJ(1:5, , 1:5)] would be a little align with subsetting arrays arr[1:5, , 1:5].
Activity
[-]binary search on selective keys in J()[/-][+]binary search on selective keys in CJ()[/+]arunsrinivasan commentedon Sep 4, 2014
I think this is a duplicate of #668 - secondary keys. Could you please verify?
jangorecki commentedon Sep 4, 2014
Arun, it depends if mentioned secondary keys would be enough to support also a longer spaces like
CJ(c(12,13,15), TRUE, TRUE, as.Date(c("2013-01-18","2013-01-31","2014-08-06")))or even bigger cases like:
CJ(4,2, TRUE, TRUE, TRUE, 6, "asd", TRUE, TRUE, "qwe")wouldn't such full table
binary-searchbe optimized for filtering queries?are there any ways emulate such process on lower level?
The one I mentioned might not scales well due to
unique(dt[,each_TRUE_col]).I will try to make some benchmarks.
The #668 is related, maybe we make new label
set2keyfor issues related to this feature.arunsrinivasan commentedon Sep 6, 2014
It takes a lot of effort to go through this example. Could you please simplify the example and make it minimal? Thank you.
Not sure I understand it completely, but in a binary search based join, if we set keys on columns
a,b,c,d, then we can not join/subset on just columnsa,b,d. We can not subset on non-consecutive columns, because they are not guaranteed to be sorted. And since it's a requirement for binary search to fetch the right value, in my understanding, this is not possible, at least with the way things are currently implemented.jangorecki commentedon Sep 6, 2014
It seems like you understand me correct.
Thanks for explanation, now I understand binary search process a little bit more. So from the technical point of view this would require second key.
So I think we can mark it as duplicate of #668.edit: I will try to address this by extendedCJversion in my DT branch.low priority
jangorecki commentedon Sep 10, 2014
binary search on selective keys addressed by #803. Closing this issue.
in terms of scalability there are other issues already related to it: #668, #804.