binary file format for pairs

[golobor]

Issue: storing Hi-C contacts in a gzipped .tsv cause major slowdowns for some computations. We need to pick a binary container and write software for common operations.

.tsv/.csv:
Cons:

• .tsv/.csv is row-oriented. Extra fields, like readID or sam_fields are really heavy, comparing to chrom and pos, yet they have to be unpacked every time a file is read through.
• text is very expensive to compress/decompress and parse. As a result, calculation of P(s) curves and other stats can take 10 minutes or more. It could potentially be done in seconds, if chrom and pos were binary.
• no random access. There is a solution, bgzip+pairix, but it has many moving parts/dependencies.

Pros:

• tsv/csv is a format that is easy to agree for a community and it is the default expectation in bioinformatics
• platform-agnostic: command-line, python, R, C, win/linux/mac - all can work with tsv, to some extent.
• can be streamed between processes via pipes
• merge-sort is available and fairly efficient for text files
• .pairs.gz is already used by the 4DN, not going away.

The alternative is to store pair tables in existing binary container files. The two options are:

HDF5:
Pros:

• a major standard, developed by a company, used by NASA, not going away
• an existing dependency, can be seen as an extension of cooler
• can store multiple tables per file: chromsizes and artifacts, like P(s) curves, trans-levels and other summaries, can be kept inside the file. HDF5 can even store non-tabular data, which could be useful for summary tables.
• easy appending, both along columns and along rows

Cons:

• columnar storage has to be implemented on top of HDF5. @nvictus has prototyped it: https://github.com/nvictus/coltab, but it needs more work. The result can potentially be popular and useful for other people and projects (including cooler?..).
• variable-length strings are not compressed, which makes them useless. The solution is to store string arrays in multiple chunks of fixed-length strings, with the length varying between chunks; the chunks could then be merged together in a virtual dataset. Requires some work to implement and maintain.
• merge-sort has to be implemented.
• very glacial development of the core format.
• there is a certain dislike of the format by the community, due to issues with parallelization and complex implementation. Both issues seem to be improving over time.

Parquet:
Pros:

• a major standard, supported by big players in IT industry. Not likely to die.
• the library is young and developed very rapidly.
• first-class support by pandas and arrow.
• supports compressed variable-length strings and dictionary compression.
• has built-in indexing of dataframes via block statistics

Cons:

• only one table per file! Chromsizes would have to be stored in the header (could be an issue for low-quality assemblies), artifacts would have to be stored in separate parquet and non-parquet files (for non-tabular data). Alternatively, we keep all related datasets together in a single zero-compression zip file, but that could be difficult to use in C/C++ and R.
• not designed for appending columns. Adding extra columns to .pairs would need a complete re-write. Appending rows seems to work, but is not preferred by design.
• merge-sort has to be implemented.
• extra dependency, though not a major one.

Personally, I'm not happy with either of the solutions. Thoughts?...

[golobor]

Update: R can read files from zip via unz() function.

[sergpolly]

New example - pod5 from nanopore https://pod5-file-format.readthedocs.io/en/latest/SPECIFICATION.html https://github.com/nanoporetech/pod5-file-format for storing raw sequencing data - several dataframes per file.
Before, they used fast5 - which is hdf5-based - same thing several tables per file, but nanopore's problem was the IO speed of hdf5.

In pod5, they "glue" several Arrow-tables (same Arrow representation as in memory - so called Feather v2 format - not as suited for long-term storage as parquet) into a custom "container" https://pod5-file-format.readthedocs.io/en/latest/SPECIFICATION.html#combined-file-layout

[golobor]

huh, looks very interesting! Do you have any idea why they didn't go with Apache Parquet+container instead?

[golobor]

some interesting observations from Twitter: https://twitter.com/Hasindu2008/status/1619914433438040065

[sergpolly]

huh, looks very interesting! Do you have any idea why they didn't go with Apache Parquet+container instead?

Not sure - but isn't parquet much more complex ? also maybe this arrow-one is still faster ? there is also that https://youtu.be/nrXoZ3NTmnU?si=aUCniTgr2bm1br0X

[sergpolly]

another slightly relevant thing: "delta lake"
https://delta.io/blog/delta-lake-vs-parquet-comparison/
https://delta.io/blog/2023-04-01-create-append-delta-lake-table-pandas/

[golobor]

huh, never heard of delta lake! Some of its advantages could be useful to us, e.g. deleting columns

[golobor]

Btw, one of the key issues has always been the lack of Out-Of-Core merge-sort for parquet files (currently, we use Unix's sort on our .tsv pairs). Two potential solutions have emerged meanwhile:

• polars: feat(rust, python): out of core sort on multiple columns pola-rs/polars#7244
• DuckDB: https://duckdb.org/2021/08/27/external-sorting.html