Designing efficient automata for CSV parsing

Bachelor’s Thesis / Guided Research

Description

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

  1. 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?
  2. 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?
  3. 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?
  4. 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

  1. The Rust csv crate (BurntSushi). github.com/BurntSushi/rust-csv
  2. Raasveldt, Mühleisen. DuckDB: an Embeddable Analytical Database. SIGMOD '19.