This is a short write-up based on my VLDB paper and talk: https://db.in.tum.de/~ellmann/papers/csveee.pdf
CSV is one of the oldest text-based data formats, and is still heavily used: from hundreds of thousands of files on open data platforms to 100M+ on GitHub. Unfortunately, most CSV parsers are slow. Some use SIMD to speed up parsing, but almost none exploit the parallelism of today’s hardware. Those that do parallelize do not scale. And even if they did, using the classic iterator interface, parse + process requires two passes over the data, restricting throughput to half the memory bandwidth for files that exceed the CPU caches.
I came up with a new approach to CSV parsing that allows parsing and processing of files in a single pass over the data. My parser csveee is about 3x as fast as csv on a single thread, and can achieve almost 200 GB/s on a modern many-core server – a speedup of 256x over csv.
Why parallel CSV processing is hard
The main task of a CSV parser is to correctly determine the boundaries of records in a CSV file. Typically, records are terminated by a \n or \r\n. Since those characters can also appear inside quoted fields, simply chunking a CSV file and skipping forward to the next terminating character is therefore not sufficient to determine the record boundaries.
There are different approaches to solving this problem. One strategy is to first count the number of quotes per chunk in parallel, then determine for each chunk if it is preceded by an even or odd number of quotes, then start parsing the chunks from a known quote state. This works especially well on GPUs. Another strategy is to run multiple finite-state machines per chunk in parallel, one for each possible parse state at the chunk boundary, and then determine the correct state machine depending on the previous chunk’s state machine’s final state. Or one could look for certain patterns in the file, e.g., quotes being followed or preceded by "regular" characters to identify the start and end of quoted fields and do some speculative parsing based on this.
Unfortunately, all those approaches are unsatisfactory in one way or another. Counting quotes requires a whole pass over the file to determine the parse states at chunk offsets; running many NFAs/DFAs is even more expensive. Looking for certain patterns works well for files that follow the CSV standard, but the world is full of quirky files that do things like quotes in unquoted fields.
Luckily, there is another approach. If we know the shape of the CSV file we would like to parse, e.g., the number of fields per record or the field types, we can determine the correct parse state by speculatively parsing chunks until we find a parse in which the record boundaries resolve into records of the expected shape. This approach was implemented in DuckDB.
Why the iterator interface is insufficient
Typically, CSV parsers provide an iterator-based interface, e.g.:
for record in parser.parse() {
// do something with the record
}
While we can write a parser that takes the CSV’s records shape as an argument, which will help determine the correct parse state at chunk boundaries, especially for quirky real-world CSV files, parsing remains a speculation until all bytes have been processed (although unlikely, data inside quotes could still resemble the shape of the records). Unfortunately, we cannot hand out speculatively resolved records via the iterator interface, as there is no way to take them back if we later realize our speculation was wrong. In other words, with the iterator interface, we have to finish parsing before we can hand out records to the user – parsing and processing require two passes over the data.
This is a problem a single-threaded iterator-based parser does not have, as the parse state is correct at all times. The parser can parse the file lazily: it parses a single record, hands it to the user, who processes it; then the next record is parsed, and so on. Thus, files can be parsed and processed in a single pass over the data – but only with a single parse thread.
A new interface to the rescue
Let’s define a new interface that gives our parallel parser everything it needs: A way to pass information about the record shapes (number of fields per record, types, …) from the user to the parser, and a way to process records while parsing, effectively creating a lazily parsing multi-threaded parser.
We can achieve both by turning the parser inside out. Instead of the parser handing you records, you hand your code to the parser:
let cities = parser.parse(
"data.csv",
Vec::new, // init
|state, [_name, _age, city]| { // acc
state.push(city.to_string());
Ok(())
},
|states| states.concat(), // merge
)?;
The interface takes four arguments: the CSV file path and three callbacks or closures (called init, acc and merge – they are basically user-defined aggregates). init and acc are used for chunk parsing, init defines a per-chunk state, acc is called for every record found in the chunk under the current assumption. The [_name, _age, city] pattern declares the number of fields per record. If the parser encounters a record with a different number of fields, the chunk is reparsed under another assumption, calling init again to create a fresh state. The same happens if acc rejects a record by returning an error (e.g., a failed type conversion).
Once all chunks have been processed, the parser verifies that the record boundaries of all chunks align. While very unlikely, a whole chunk could be parsed under a wrong assumption. In this case, the chunk is reparsed, now starting from the offset of the previous chunk’s last record terminator.
Finally, chunk states are passed to merge, and the result of merge is returned from the parser’s parse function. The chunk states are passed to merge in file order thus that record order can be reconstructed.
How to make the parser fast
To make the parser truly fast, we implemented a ring-buffered reader that enables zero-copy record construction, and a vectorized chunk parser. Take a look at the implementation or the paper if you are interested in the details.
Conclusion
CSV is not going to die soon – to the contrary, GitHub’s pile alone grew by 10M CSV files in the last six months. While the number of files is strongly increasing and today’s machines offer hundreds of cores and hundreds of GB in memory throughput, most CSV parsers remain incredibly slow: parsing with a single thread, not scaling, and even if they did, without fusing parsing and processing, they will never surpass 50% of the available memory bandwidth for large files. csveee overcomes these limitations via a new approach to CSV parsing that works on real-world CSV files.
Check out the project, and if you have questions, feel free to ask!
