> The intuition is that for datasets commonly and frequently joined on a known key, e.g., user events with user metadata on a user ID, we can write them in bucket files with records bucketed and sorted by that key. By knowing which files contain a subset of keys and in what order, shuffle becomes a matter of merge-sorting values from matching bucket files, completely eliminating costly disk and network I/O of moving key–value pairs around.
I'm actually surprised that this should be regarded as "novel" in data science.
It reminds me of something in Eric Raymonds "The Art of Unix Programming" (I don't have time to find the link right now) where it discussed an approach from the earlier days of Linux filesystems where you had a limit on the number of iNodes that could exist in a single directory and corresponding performance. The work around was to create a subdirectory structure to store files based on the filename. But then you tended to get many files starting with the same characters all in the same directories. What turned out to be a better way to distribute the files evenly in the directory structure was to take the first and _last_ character of the file name and use those to create the subdirectories. This way you were more likely to spread the files evenly across the structure.