Designing efficient automata for CSV parsing
Bachelor’s Thesis / Guided ResearchDescription
CSV is still one of the prevalent formats for tabular data: Amazon Redshift reports that external data is mostly CSV, GitHub contains over 90 million CSV files, open data platforms host hundreds of thousands datasets as CSVs. Unfortunately, today's single-threaded CSV parsers are quite slow. To overcome this bottleneck, we have built a very fast (>100 GB/s) parallel, vectorized CSV parser; a paper describing our approach is currently under revision at VLDB.
The vectorized path handles the common case. To cover the long tail of dialects — files without a fixed field count, comment or empty lines, field trimming, etc. — we have extended our approach with a DFA implementation. The DFA works and is reasonably fast, but it was written pragmatically and has not been studied on its own.
The aim of this thesis is to take a deeper look at finite-automaton designs for CSV
parsing: to survey what existing parsers do (e.g., the Rust csv crate [1] and DuckDB
[2]), implement alternative automaton
designs, and characterize their trade-offs across differently shaped inputs — with
the goal of identifying a good automaton for CSV parsing. The work can be
carried out as a standalone study or directly on top of our parallel parsing
infrastructure.
Research questions
- What automaton designs do existing CSV parsers use (Rust
csv, DuckDB, others), how do their choices differ — state encoding, transition representation, handling of quoting/escaping, and the strategy for skipping non-structural bytes? - How do different automaton designs compare in throughput, and how does the ranking change with the shape of the input — field width, quoting density, escape frequency, number of columns, record length?
- Where does the time actually go? For a given design, how much of the cost is the automaton itself versus scanning non-structural bytes, output compaction, and memory bandwidth?
- Can a single design be picked as a good default, or does the best choice depend on the dialect and data shape strongly enough to justify selecting (or generating) the automaton at parse time?
Prerequisites
- Knowledge of a systems programming language (C, C++, Rust, …)
- Interest in low-level performance engineering and careful benchmarking
Contact
If you are interested in this topic, send me an e-mail or drop by my office.
References
- The Rust
csvcrate (BurntSushi). github.com/BurntSushi/rust-csv - Raasveldt, Mühleisen. DuckDB: an Embeddable Analytical Database. SIGMOD '19.