3 ms·

Any info on whether it does this in a streaming manner? For small files there are a plethora of solutions, but it gets more tricky / interesting when you can't

by zmmmmm 7y ago

Any info on whether it does this in a streaming manner? For small files there are a plethora of solutions, but it gets more tricky / interesting when you can't assume both files fit in memory and (ideally) you want to do it in a single pass because I/O itself is a bottleneck.

goodside 7y ago
If the files are sorted, merge in Python (`heaps.merge` or `sorted` on chunks plus `itertools.groupby`). If they’re not sorted, a single pass is mostly out of the question — you need out-of-core sorting. GNU sort with intermediate compression of temporary/intermediate files is hard to beat there for performance, but if your join keys are more complicated than can be specified in GNU sort you need a more involved pipeline. If raw IO is actually the bottleneck, that’s usually a sign you need better compression — look into Zstandard and lz4, especially for intermediate files. If IO is still the bottleneck, consider possible sharding keys (Python ‘hash’ plus modulo works well, or CRC32 etc.) that would let you divide the problem up among a large number of workers. Everything is easier if you get the data into S3 storage early.
burntsushi 7y ago
It's almost done in a streaming fashion. `xsv join` uses memory proportional to the number of records in one of the inputs and the size of the join columns in one of the inputs. Namely, it creates an in-memory map from the join column's values to the corresponding record index. Combined with another in-memory index that maps record index to the corresponding record's byte offset, it can jump to the corresponding record in constant time while streaming over the other input. There are better ways to do this that don't involve using this much memory, but this struck a good balance between memory usage and implementation complexity. I may improve on this some day. So basically, as long as you have enough memory to store the entire join columns along with `8 * len(one_input)` bytes for the record index, then you should be good.
- zmmmmm 7y ago
  great! It may address some particular cases that I don't have a good tool for currently then. Thanks!

by zmmmmm 7y ago

goodside 7y ago

If the files are sorted, merge in Python (`heaps.merge` or `sorted` on chunks plus `itertools.groupby`). If they’re not sorted, a single pass is mostly out of the question — you need out-of-core sorting. GNU sort with intermediate compression of temporary/intermediate files is hard to beat there for performance, but if your join keys are more complicated than can be specified in GNU sort you need a more involved pipeline. If raw IO is actually the bottleneck, that’s usually a sign you need better compression — look into Zstandard and lz4, especially for intermediate files. If IO is still the bottleneck, consider possible sharding keys (Python ‘hash’ plus modulo works well, or CRC32 etc.) that would let you divide the problem up among a large number of workers. Everything is easier if you get the data into S3 storage early.

burntsushi 7y ago

It's almost done in a streaming fashion. `xsv join` uses memory proportional to the number of records in one of the inputs and the size of the join columns in one of the inputs. Namely, it creates an in-memory map from the join column's values to the corresponding record index. Combined with another in-memory index that maps record index to the corresponding record's byte offset, it can jump to the corresponding record in constant time while streaming over the other input. There are better ways to do this that don't involve using this much memory, but this struck a good balance between memory usage and implementation complexity. I may improve on this some day. So basically, as long as you have enough memory to store the entire join columns along with `8 * len(one_input)` bytes for the record index, then you should be good.

zmmmmm 7y ago
great! It may address some particular cases that I don't have a good tool for currently then. Thanks!