Efficient encoding for List<Categorical>

[gatesn]

A common use-case is to store a column containing "tags" where the tags have relatively low cardinality and each row stores a list of these tags.

e.g. the statpopgen FILTER column

┌────────────────┐
│     FILTER     │
│   varchar[]    │
├────────────────┤
│ [AC0, AS_VQSR] │
│ [AC0, AS_VQSR] │
│ [AC0, AS_VQSR] │
│ [PASS]         │
│ [AS_VQSR]      │
│ [AS_VQSR]      │
│ [AS_VQSR]      │
│ [AS_VQSR]      │
│ [AS_VQSR]      │
│ [AS_VQSR]      │
├────────────────┤
│    10 rows     │
└────────────────┘

In this case, there are actually very few unique sets of tags:

D select distinct FILTER from 'bench-vortex/data/statpopgen/100000/parquet/gnomad.genomes.v3.1.2.hgdp_tgp.chr21.parquet' LIMIT 100;
┌────────────────────────────┐
│           FILTER           │
│         varchar[]          │
├────────────────────────────┤
│ [AS_VQSR]                  │
│ [AC0, InbreedingCoeff]     │
│ [AC0]                      │
│ [AC0, AS_VQSR]             │
│ [PASS]                     │
│ [InbreedingCoeff]          │
│ [AS_VQSR, InbreedingCoeff] │
└────────────────────────────┘

But I don't think this generally holds true?

So what should a good Vortex encoding be for this column? And is there a sensible Arrow data type that we can decompress into?

[gatesn]

So here's a proposal:

Take the array:

[A]
[A, B]
[B, C]
[A, C]

We can encode as a ListView { elements: Dictionary<Utf8> }

ListView:
  elements:
    Dictionary:
      values: [A, B, C] # All unique tags are stored only once
      codes: [0, 1, 2, 0, 2] # Codes stores all unique "runs" of tags
  offsets: [0, 0, 1, 3] # Note how [A, B] and [B, C] overlap in the dictionary codes.
  sizes: [1, 2, 2, 2]

[agola11]

Thanks @gatesn! How would this work in practice? Would we have to construct a values Array and codes Array manually, then create a DictArray from those two arrays?

Would we then construct a ListViewArray from the DictArray assuming we know offsets and sizes?

I am assuming we would have to construct the arrays manually and write them into a flat layout strategy since we are doing the dictionary construction at the array level.

[infogulch]

we would have to construct the arrays manually and write them into a flat layout strategy since we are doing the dictionary construction at the array level

I'm curious about this as well since Vortex advertises separation between logical and physical layouts. Does that capability extend to encapsulating this (relatively) complicated physical layout and exposing a simpler "logical" layout that looks more like a column of an array of strings?

[connortsui20]

@infogulch You bring up a good point that this can get complicated very fast!

One thing we can do to make it less complicated for the consumer of this type is to model this as a DType::Extension and abstract away a bunch of the nastiness in dealing with a nested type.

As an aside to be pedantic (sorry!), note that we define the in-memory representation as an encoding (which is physical), where "layout" means something different. The diagram above shows us a physical encoding tree, where the logical DType of the data would be DType::List(DType::Utf8).

So for any consumers, they can treat this data an an array/column of DType::List(DType::Utf8) data. The reason we are talking about the physical encoding is that if we fully decompressed the array tree (what we call canonicalizing), we might be duplicating a bunch of data that we don't need by repeating all of the string tags over and over again.

[infogulch]

I'm fully onboard with the idea that certain (perhaps "esoteric" rather than "nasty") ways to factor out duplications is 💯 the best way to maximize compressibility. This proposal in particular looks excellent to me at first glance. (Though it's probably a good idea to run some experiments anyway.)

I was hoping you'd be pedantic so I could understand better, thank you! Your explanation answers exactly what I meant to ask, because for this to work out in practice you need both a simple conceptual datatype that end users interact with and the complex origami folding of the data into some esoteric layout that maximizes compressibility. I'm excited for Vortex because it aims to bridge this gap.

Sorry, I didn't mean to distract from the main topic!

[connortsui20]

No that's totally fine! In fact one of the "meta" goals for next year is to formalize the concepts in Vortex because, as you have found at first hand, they are quite complicated and even we haven't fully figured it out ourselves.

[gatesn]

@agola11 - yes I would say this logic should be wrapped up a specific compression strategy. So essentially a custom builder that you can push arrays into that will be converted into this form. Then we need some way to either infer this strategy, or probably easier is to prescribe this strategy. e.g. use a CompressorWriteStrategy that you pre-configured to run this specific encoding function.

[infogulch]

This listview design opens two degrees of freedom that might be worth exploiting to maximize compressibility:

1. The permutation of strings in ListView.elements.Dictionary.values
2. The codes list, which should probably approach a de Bruijn sequence as the number of substrings present in the input data covers all possible combinations. (See some generic de Bruijn generators I found 1, 2).