improve filesort()

Taking a look at the file based sort now, and recording observations and design notes here as I go.

Current implementation

based on bucket sort

1. Manager reads the first nsamp=1000 rows of file (or a sample of distributed data frame)
2. Manager uses quantiles to choose approximately equal sized bins based on sample
3. Each worker reads all the data in and keeps only those that belong to its chunk
4. Each worker sorts it's chunk and makes it a global variable outdfnm

Notes

1. Data must fit in memory on the cluster
2. The entire data is read k times, once for each of the k workers.

Alternative 1: Single read

data.table has high performance reading and sorting using multithreading. If the data will fit in memory then it may well be faster to read and sort in the manager, then send to the workers using distribsplit().

Alternative 2: Temporary file based

Use steps 1 and 2 in the current implementation to determine bins. Then:

1. Assign each worker a subset of the distributed files to read and split
2. Each worker reads these files in chunks, splitting the chunk and appending into it's own private set of bins. This results in the following temporary directory structure:

- worker1
    file_bin1
    file_bin2
    ...
- worker2
    file_bin1
    file_bin2
    ...
etc.

Finally, each worker is responsible for reading and sorting a subset of the bins. If there are more bins than workers then we can write the sorted files to disk without requiring that the data fit in memory. This approach requires 2 reads and 1 write, instead of k reads.

Start by reading the filesort() implementation and the current bucket-sort flow described here, including distribsplit() and the data.table comparison. The issue records alternatives but does not define a selected design or acceptance criteria, so a contributor would need maintainer guidance before identifying what “done” means.