Internal Representation (row/column based)

[multimeric]

• A single internal consisting of a collection of row structs repr will severely hinder performance with the columnar formats
• On the other hand, moving to columnar IR will hinder the row-based formats
• On the third hand, having two or more different IRs will make the codebase difficult to maintain and confusing

[multimeric]

My solution at the moment is to allow the IR to vary with the serialization target. For example this means we would use Arrow internally when dealing with Feather and Parquet etc, as well as the native IR for Avro, ORC etc.

The reason I think this is a fine solution is because we don't actually have a long term goal of providing translation between multiple different next gen formats. We only need translation between "traditional" (e.g. BED, VCF) and "the best" next gen format, e.g. Parquet, Feather etc. By untethering the serde format from the IR, we guarantee maximal performance.

This solution does admittedly detract from the "Rosetta Stone" metaphor we had going, but I think it's the best option we have.

Of course we'll need to see what everyone thinks of this ideal (@brainstorm).

[brainstorm]

That makes a lot of sense, Michael. In my mind I was focusing on perf for the output format usage (and show it is consumed/processed faster than traditional ones), but thanks to Gabriel and you now we can also get better performance on the conversion side.

Thumbs up with this idea, makes sense to lose generality we don't really need in favor of perf.

[GabrielSimonetto]

Yea, if performance is a priority for us, probably 2 different IR's may be the way to go.

But sometimes we will have to pay the price of going from row format to columnar format anyhow right? I mean, if we go from BED -> BioSerde Columnar IR -> Parquet, it can be just a question of making the transition one step to columnar earlier or later (on the bioserde IR phase, and on the parquet phase). But, of course, If we ONLY have the row based IR, we have a problem if we are going from columnar format to another columnar format, paying the price for 2 useless transitions. Does that sound like a correct assumption?

[multimeric]

To be clear, I don't mean 2 different IRs. I mean $n$ different IRs, where $n$ is the number of formats we look at. My idea is that we dispense with using our own structs entirely, and just use the types provided by each of the format libraries.

But sometimes we will have to pay the price of going from row format to columnar format anyhow right?

Yes, since all the text formats are row based because of how text works, any conversion from text to columnar will invoke this penalty. But you must remember that format conversion is not the only thing we're benchmarking. We also want to test operations from Parquet to Parquet such as "find the record containing this string", and "count the number of records" and "find all records that overlap this region". In these cases, we won't encounter any penalty at all because there's no format conversion required.

[multimeric]

Copying my draft implementation here:

trait BioSerde {
    fn save(&self, path: std::path::Path);
    fn load(path: std::path::Path) -> Self;
}

trait BedFileRegion {
    fn get_reference() -> String;
    fn get_start() -> u64;
    fn get_end() -> u64;
    // etc
}

trait<T> BedFileOps : BioSerde where T : BedFileRegion {
    fn iter_regions() -> IntoIter<T>;
    fn regions_at(reference: &str, start: u64, end: u64) -> IntoIter<T>;
    // These will depend on the type of benchmarks we want
}

impl BedFileOps for arrow::record_batch::RecordBatch {
    // These will involve `.zip`ing all the arrays in the batch
}

Note how I'm impl BedFileOps for arrow::record_batch::RecordBatch, so we have no need for our own struct.

[multimeric]

I realise that I hadn't thought much about how we will do the format conversions under this proposed scheme, only the benchmarking. So I've realised that this can just be implemented by a save_bam/load_bam type of function in each of the traits corresponding to each format. Notably, one thing I've changed is that I've removed the BioSerde trait, because the way that we save to parquet etc will vary depending on the class of bioinformatics data we're saving, so it needs to live inside the specific Ops trait. Here's another sketch of how I'm envisaging this:

// This lets us re-use the same code for parquet and feather
enum ArrowSerializationFormat {
    Parquet,
    Feather
}
// Technically this is our own IR, but it's just a very light wrapper around RecordBatch
struct ArrowIr {
    batch: arrow::record_batch::RecordBatch,
    format: ArrowSerializationFormat
}

// These traits represent the ability to do things relating to a specific domain in bioinformatics
trait AlignmentOps : BioFormat {
    // We need any alignment format to be able to interop with BAM
    fn load_bam(path: Path) -> Self;
    fn save_bam(&self, path: Path);

    fn save_native(&self, path: std::path::Path);
    fn load_native(path: std::path::Path) -> Self;

    // This is the stuff we will benchmark
    fn reads_at_position(reference: &str, start: u64, end: u64) -> IntoIter<T>;
    fn iter_reads() -> IntoIter<T>;
}

// Here's another example of a different format Ops trait
trait SequenceOps {
    fn load_fasta(path: Path) -> Self;
    fn save_fasta(&self, path: Path);
    fn save_native(&self, path: std::path::Path);
    fn load_native(path: std::path::Path) -> Self;
}

// All the implementation for a given format will live in here
impl AlignmentOps for ArrowIr {
    // Save to parquet or feather
    fn save_native(&self, path: std::path::Path);
    // Load from parquet or feather
    fn load_native(path: std::path::Path) -> Self;
    // Using Noodles for these
    fn load_bam(path: Path) -> Self {}
    fn save_bam(&self, path: Path) {}    
}

Here's a draft of the conversion process:

graph TD
    A[Arrow IR]:::IR;
    B[Parquet File]:::NextGen;
    C[Feather File]:::NextGen;
    D[BAM File]:::Primitive;
    E[Avro IR]:::IR;
    F[Avro File]:::NextGen;

    A -- "save_native" --> B;
    B -- load_native --> A;
    A -- save_bam --> D;
    D -- load_bam --> A;
    A -- save_native --> C;
    C -- load_native --> A;
    E -- save_native --> F;
    F -- load_native --> E;
    E -- save_bam --> D;
    D -- load_bam --> E;

    classDef IR fill:orange;
    classDef NextGen fill:white;
    classDef Primitive fill:skyblue;

Loading

[multimeric]

Let me know if you think this makes sense, @brainstorm.

[brainstorm]

Michael, thanks so much for your architecture proposal. I think that Arrow as IR makes sense let me point out a couple of changes that, me and @chris-zen (previous GSoC htsget-rs mentor) think that can improve its maintenance, scalability and DX after having a quick chat about what you are proposing:

1. Higher level abstractions: More abstract reader/writer/iterator traits exposed to the developer instead of multiple per-format abstractions.
2. (pub) Method naming: serialize/deserialize instead of load_, save_ and native_ methods.

Point 1 is specially important from the perspective of adding formats in the future: we don't need to break traits/contracts on each release. Instead, providing a Serializer/Deserializer to the user (i.e like Noodles does) would give us room to iteratively optimize the inner structures and methods without breaking compatibility. This comes at the possible cost of not being as fast with the conversion itself, but I think that performance on use and consumption of the resulting output format should have higher priority.

If we adopt this Reader/Writer model, the internal shape of the IR is not as important as the contract itself. So essentially a Box would be the common binary exchange between readers and writers. Other than those readers and writers, the trait should just provide an iterator for the "data records" we have in the origin format (rows, columns, records...).

I hope that makes sense?

/cc @zaeleus @mmalenic

[multimeric]

More abstract reader/writer/iterator traits exposed to the developer instead of multiple per-format abstractions.

I think I need to see a proposed architecture for this before I can fully comment. I'm not sure where the API fragility is that you're talking about. I consciously put all this functionality into the *Ops traits because the read/write/iterate methods must vary with each type of data we're representing. It makes little sense to have an alignment-type parquet file share an implementation with a fasta-type parquet file.

Method naming: serialize/deserialize instead of load_, save_ and native_ methods.

I have no issue with this change. There's also room to negotiate the signature of these functions (should they accept a Path, or a buffer of some sort?)

[brainstorm]

A bit harsh but very fair criticism, @multimeric. Let's switch to code instead so perhaps we can get this up and running faster?

See draft PR #10.

Admittedly, there's more work to be done there w.r.t how to handle the lower level details and auxiliary (non-public) traits, but the point I was trying to get across is that we should imagine how users will be interacting with BioSerDe before going into the lower level implementation bits, otherwise those impl details will leak into higher level abstractions (non desirable).

Please @GabrielSimonetto @E-Allie, jump in into this discussion and/or push some commits directly to the aforementioned PR fearlessly as this architecture will be the one you'll be working on for the next few months, so you are the main stakeholders here ;)

[multimeric]

Sorry, I'll try to be less critical. Yes, we can try to negotiate the balance between public and private traits in the concrete code.

[GabrielSimonetto]

For the past couple of days I've been iterating on #10, and I think I have some stuff to add to the conversation.

Here is a playground about my best effort to serialize the proposed ModernBioFormat struct, the main problem seems to be the definition of how we will be serializing a writer object.

When that wasn't working, I went on to draft a more specific bed to bed conversion, to see if the concrete definitions would help analyze the architecture proposals, and it really feels like we will need to make a trait definition of which writers and readers we are ready to deal with.

It may just be that I heavily missed some points in the discussion, if there is something that I am clearly missed you are welcome to point that out.

I point out in the PR draft #11 that we still have the problem of dealing with heavy contraints in the particular crates about how to insert the records to be written (In noodles-bed case, it has to be a specific struct defined by them, and not any generic data that we could pass directly, which should be the case for the other modern formats aswell). When I initially looked at the ModernBioFormat I was thinking that maybe the data would be already inside the writer object, but now I am not so sure. Should the data have a generic placeholder in the ModernBioFormat struct aswell (or whatever name the final main struct ends up having)?

Looking forward for your feedback, @brainstorm, @multimeric.

[brainstorm]

Thanks Gabriel, what you've found is consistent with some of my latest experiments and previous experience in the last comments of this thread.

I've re-started this issue thread, I think it might be valuable to have some work done on Noodles first if possible.

[brainstorm]

@GabrielSimonetto, here's some experimental scaffold of reader/streaming based traits I discussed with @chris-zen, former mentor of GSoC. I still think that going for SerDe-provided interfaces and building up from there would be preferable though.

Even if we initially load all the file contents on memory, we can optimize later. I'll examine your most recent commit(s) tomorrow and comment on them.

// lib.rs

trait RowReader<Row> {
    type RowIterator;

    fn iter(&self) -> Self::RowIterator<Row>;
}

trait RowWriter<Row> {
    type Error;

    fn write<R: RowReader<Row>>(&mut self, reader: R) -> Result<(), Self::Error>;
}


// bam_reader.rs --------------------

use noodles::bam::AsyncReader as BamAsyncReader;


struct BamReader {
    reader: BamAsyncReader,
}


impl BamReader {
    pub fn new(reader: BamAsyncReader) -> Self {
        Self {
            reader
        }
    }
}

impl RowReader<SequenceRead> for BamReader {
    type RowIterator = BamRowIterator<BamRecord>;

    fn iter(&self) -> Self::RowIterator {
        BamRowIterator {
            reader: &self.reader
        }
    }
}

struct BamRowIterator<'a> {
    reader: BamAsyncReader<'a>,
}

impl<'a> Iterator<Item=BamRecord> for BamRowIterator<'a> {
    fn next(&self) -> Option<&Self::Item> {
        // self.reader.next()
        todo!()
    }
}

// arrow_writer.rs --------------------

struct ArrowWriter {
    writer: arrow::Writer;
}

impl ArrowWriter {
    pub fn new(writer: arrow::Writer) -> Self {
        Self {
            writer
        }
    }
}

/// reads -> BAM, CRAM... 
impl RowWriter<SequenceRead> {
    type Error = ArrowError;

    fn write<R: RowReader<SequenceRead>>(&mut self, reader: R) -> Result<(), Self::Error> {
        let iter = reader.iter();
        for seq_read in iter {
            let data = sequence_read_to_arrow(seq_read)?;
            self.writer.write(data)?;
        }
        Ok(())
    }
}

/// variants -> VCF, BCF
impl RowWriter<Variant> {
    type Error = ArrowError;

    fn write<R: RowReader<Variant>>(&mut self, reader: R) -> Result<(), Self::Error> {
        let iter = reader.iter();
        for variant in iter {
            let data = variant_to_arrow(variant)?;
            self.writer.write(data)?;
        }
        Ok(())
    }
}

// ----------------------

use noodles::vcf::AsyncReader as VcfAsyncReader;

// VariantRecord??
// /reads -> BAM, CRAM... 


struct ParquetWriter {}
struct ArrowWriter {}

impl RowWriter for ArrowWriter {
    type Error;

    fn write<R: RowReader>(&mut self, reader: R) -> Result<(), Self::Error> {
        todo!()
    }
}

struct FastqReader {}