NVIDIA / NVIDIA/cudf

[FEA] `read_csv` context-passing interface for distributed/segmented parsing

Open
#11,728 8 comments 1 reaction 1 assignee Claimed by @upsj View on GitHub
cuIO feature request libcudf
Dominant language
C++
Stars
9.8k
Forks
1.1k
Avg merge
3d 6m
Merged PRs (30d)
278

Description

**Is your feature request related to a problem? Please describe.**
To parse files from a regular language like CSV, we can only safely parse data inside a byte range if we know the parsing context from before this range. Without this information, we may accidentally interpret a record delimiter (newline) inside a quoted field as an actual delimiter.

More formally, when starting from a byte range, we don't know what state the DFA of the token language is in, so we need to store the transition vector starting from every possible state, and combine the vectors by function composition in the associative scan operation. This is pretty much identical to what is happening in [the finite state transducer](https://github.com/rapidsai/cudf/pull/11242).

Instead of just running the scan on a full file, we can run it only on a byte range, and combine the resulting transition vectors in an exclusive scan over all byte ranges to establish local parsing context.

**Describe the solution you'd like**
I want to propose a slight extension to the `read_csv` interface to handle this case:

1. add a `class csv_parse_context` that opaquely wraps `packed_rowctx_t`, only exposing the `merge_row_contexts` functionality to combine the parsing context from adjacent byte ranges, and a `finalize` operation that turns the transition vector into its value starting from the initial DFA state.
2. add a `read_csv_context` function that only scans the local byte range to compute its `csv_parse_context` transition vector. It can probably take the same parameters as `read_csv`
3. add a `csv_parse_context initial_parsing_state` parameter to `csv_reader_options` that defaults to the initial state. The `read_csv` function can then use this initial state to determine record offsets and do the actual parsing.

**Describe alternatives you've considered**
Alternatively, we could implement backtracking by reading chunks before the byte range until we figured out an unambiguous parser state (that is not the error state). This could in the worst case lead to reading the entire prefix up to the byte range.

**Additional context**
This is relevant if we want `dask.read_csv` to be able to handle quoted record delimiters (i.e. newlines) where the opening quote occurs before the byte range.

The interface has the advantage that it can be tested in isolation on a single node, without having to rely on dask.

The same kind of pattern could also apply to `read_json`, where on top of the regular parsing state, we also need to pass the stack transition operations from the beginning to the end of the byte range.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.