setkey and the := operator, data.table, R

Question

When using the data.table package, I am a bit unsure of when i need to setkey(). For example, when using the := operator with the by option, things seem to still be very fast even though I have not set a key. Could someone please elucidate when setkey() is necessary and when it is not? And if it is not necessary prior to calling := with by then how is the data.table package so fast since presumably it has to do the same thing as apply in standard data.frame R by doing a sequential search rather than a binary one since it doesn't know whether my data.table is actually sorted by the argument to by.

Thanks

Answer 1

These 2 FAQs seem close :

3.2 I don't have a key on a large table, but grouping is still really quick. Why is that?
data.table uses radix sorting. This is signicantly faster than other sort algorithms. Radix is specifically for integers only, see ?base::sort.list(x,method="radix"). This is also one reason why setkey is quick. When no key is set, or we group in a different order from that of the key, we call it an ad hoc by.

3.3 Why is grouping by columns in the key faster than an ad hoc by?
Because each group is contiguous in RAM, thereby minimising page fetches, and memory can be copied in bulk (memcpy in C) rather than looping in C.

What it doesn't say, and probably should do, is that you need a very large dataset, where each group is also very large, before you notice the difference between keyed by and ad hoc by. Something like 100 groups of 100MB each (a 10GB data.table) such as 1e8 rows and 13 columns. Otherwise, there is no need to setkey first, especially since that can get onerous.