A Fast Path for Fixed-Length Lists in Parquet - Gunnar Morling

[giscus[bot]]

A Fast Path for Fixed-Length Lists in Parquet - Gunnar Morling

In its current form Apache Parquet isn’t a great fit for storing fixed-length lists, such as coordinates, RGB(A) colors, or—​an increasingly common case—​vector embeddings driving search and …

https://www.morling.dev/blog/fast-path-for-fixed-length-lists-in-parquet/

[mghildiy]

Nice explanation. Thanks.

[gunnarmorling]

Thank you!

[rok]

Nice experiment and writeup, thanks!
Two questions:

• If you sweep list size further into 10**6 range, what do results look like?
• If some lists are null (the entire list, not individual elements) are some optimizations like this still possible?

[gunnarmorling]

Hey @rok, good questions.

If you sweep list size further into 10**6 range, what do results look like?

I ran again for list sizes of 1,000, 10,000, 100,000.

For 10K, the fast path still matches the flat floor; for 100K it is a bit slower than that, but still a significant improvement over the base lines of both row and column readers:

ASCII chart — ms/op (lower is better)

  FixedSizeListScanBenchmark — 1000
    columnBaseline        │███████████████████ 382.8
    columnFast            │████████ 160.3
    flatFloor             │████████ 163.2
    rowBaseline           │██████████████████████████████ 599.5
    rowFast               │████████ 162.8

  FixedSizeListScanBenchmark — 10000
    columnBaseline        │███████████████████ 362.9
    columnFast            │█████████ 164.2
    flatFloor             │█████████ 162.9
    rowBaseline           │██████████████████████████████ 567.8
    rowFast               │█████████ 165.8

  FixedSizeListScanBenchmark — 100000
    columnBaseline        │████████████████████ 388.0
    columnFast            │██████████ 202.9
    flatFloor             │████████ 163.7
    rowBaseline           │██████████████████████████████ 583.8
    rowFast               │██████████ 203.4

If some lists are null (the entire list, not individual elements) are some optimizations like this still possible?

I think so, yes. Most importantly, we could still bulk-copy values (a null list stores no values). The detector logic would be more costly to run, though. Worth trying if someone has the need, I'd say.

[rok]

For 10K, the fast path still matches the flat floor; for 100K it is a bit slower than that, but still a significant improvement over the base lines of both row and column readers:

Thanks! Is this normalized per row or entire column? (it says ms/op) If not it's odd that the trend doesn't linearly continue give more than 2x improvement. Do you think it's some memory handling or shifting issue that can be worked around?

If some lists are null (the entire list, not individual elements) are some optimizations like this still possible?

I think so, yes. Most importantly, we could still bulk-copy values (a null list stores no values). The detector logic would be more costly to run, though. Worth trying if someone has the need, I'd say.

I'm thinking of random reads of large vectors with per-row nullability. I suppose the scan wont be the most expensive part of such a read.

[gunnarmorling]

Thanks! Is this normalized per row or entire column? (it says ms/op)

It's the time for scanning the entire file (~500 MB, 128M total values, distributed to 128M/k records).

If not it's odd that the trend doesn't linearly continue give more than 2x improvement. Do you think it's some memory handling or shifting issue that can be worked around?

Not 100% sure what exactly the limiting factor is at this point; It shouldn't be memory bandwidth, I suppose the consumer-side fold in the benchmark itself is a key factor.

I'm thinking of random reads of large vectors with per-row nullability. I suppose the scan wont be the most expensive part of such a read.

Agreed, there's probably something to be gained here. Contributions welcome :)

[rok]

Agreed, there's probably something to be gained here. Contributions welcome :)

If get a useful idea I'll try to contribute it!