Measure best case performance for the new thrift-remodel / custom thrift parser

[alamb]

Which part is this question about

Related to

• Use custom thrift decoder to improve speed of parsing parquet metadata #5854

On the parquet list there is a discussion about potentially adding a new flatbuffers based format to replace/augment the existing thrift encoding from @alkis: https://lists.apache.org/thread/1v2ww0w5956j6p64wgp6sdbo5sw7lcp6

Andrew, do you have a more precise estimate for the speedup we could expect
in C++? It's also important to note that Thrift's format does not allow for
random access, meaning we will always have to parse the entire footer,
regardless of which columns are requested.

This is a commonly raised concern about the current thrift format, which is that the footer must always be scanned due to thrift's

The same thread estimates using a flatbuffers footer achieves a 20x (10x * 2) improvement for the 99.9'th percentile:

Even with this conversion, we're observing a
greater than 10x improvement in footer decoding time for footers that
perform poorly with Thrift (at the p999 percentile). Removing the
FileMetadata translation should easily provide another 2x speedup.

Describe your question

What is the best case performance improvement our custom thrift parser over the existing thrift parser can achieve? Specifically, how close is it 20x?

Here is what I think is the best case:

1. A file with many columns (10,000 to 100,000)
2. Written with statistics (both in the ColumnChunks and Page/Column index)

The comparison is:

1. Load ParquetMetadata using the existing ParquetMetadataReader
2. Load ParquetMetadata with the new reader, and only parse the necessary fields (e.g. skip over statistics, etc)

Additional context

The question asks about the C++ performance, which while is important, is not something I have time to pursue, I am only interested in the Rust implementation for now.

[alamb]

@etseidl do you think the thrift-remodel branch is up for this test? I can write the harness potentially, but I wanted to ask you to save time (aka be lazy) if the branch is ready yet (I could just hard code skipping stats for now)

[alamb]

As I say on the list, It will be fun to benchmaxx our new parser 🤪

[etseidl]

The remodel is in the home stretch, and I don't think there are major changes left on the read side, so we're likely about ready to start on the testing you'd like to do. What I'm finding now is that skipping fields is about 2X faster than decoding them (depending on the field ofc), and the new thrift decoding is about 2-3X faster than that generated by the thrift compiler. For a simple case (alltypes_tiny_pages, 10-ish columns), it seems the time is evenly split between thrift decoding and subsequent translation to metadata objects. For the 10000 column case in the benchmark, the thrift decoding is more like 80% of the time, but I'm starting to not like that bench so much because I noticed it's using a RNG for many of the fields, so we're getting negative numbers that are requiring far more bytes to store than you'd see in practice. I need to fix that up, but perhaps your test rig can do a better job as well.

I do feel that the lack of random access is a bit of a red herring. I don't know offhand what changes Alkis made to the metadata for the flatbuffer test, but if it's the same form as the current metadata I don't see how he'd be able to skip decoding the whole thing. If he's recast it in a more columnar way, then I think an apples-to-apples comparison would be to produce an index for the row groups and column chunks. If we know the start and end of each we can simply grab the appropriate slice of data and parse it, just as we do now with the page indexes.

Anyway, thrift is more complicated that flatbuffers, so we'll never get to 20X improvement, but I could see 5X as we have for the column index, and perhaps if we skip structures like the column chunk statistics and the page encoding stats (that one is a very heavy hitter).

I'd also note that the flatbuffers parser totally ignores the page indexes AFAICT, and also omits the most expensive structures in the current metadata, so I think the 10X number is a bit unfair to bandy about. I'm sure we could rewrite the current metadata structures in a more friendly to parse way and see similarly spectacular improvements.

[alamb]

I do feel that the lack of random access is a bit of a red herring. I don't know offhand what changes Alkis made to the metadata for the flatbuffer test, but if it's the same form as the current metadata I don't see how he'd be able to skip decoding the whole thing.

Yes I feel the same way

I'd also note that the flatbuffers parser totally ignores the page indexes AFAICT, and also omits the most expensive structures in the current metadata, so I think the 10X number is a bit unfair to bandy about. I'm sure we could rewrite the current metadata structures in a more friendly to parse way and see similarly spectacular improvements.

Yeah, this is what I would like to try and do -- cook up the best possible case.

For example, I am imagining 10k string columns with column chunk statistics, and then using our custom thrift parser to skip the stats (and thus skip allocating strings)

So for a file with 100 row groups, skipping the stats is going to save 100 * 10k = 1M allocations. I have to imagine we can see similarly spectacular numbers by doing that much less work 😆

[etseidl]

FWIW I spent this afternoon wringing a little more performance out of the skipping code. Managed to get another 25% at least.

[alkis]

I do feel that the lack of random access is a bit of a red herring. I don't know offhand what changes Alkis made to the metadata for the flatbuffer test, but if it's the same form as the current metadata I don't see how he'd be able to skip decoding the whole thing.

Random access is indeed a red herring.

The differences between flatbuf and thrift are:

1. Thrift has to parse the bytes and put them in a generated (or custom) struct in memory. This translates to major overheads in:
   a. memory allocations for dynamic parts of the struct: vector, string in C++ parlance
   b. most of the bytes need to be touched: integers are varints, they have to be parsed, strings can be skipped, arrays can be skipped
2. Flatbuf does not need to parse the bytes and perhaps more importantly does not have to move the bytes to a generated (or custom) structure in memory. A field access involves some pointer chasing on relative offsets (this is what gives it the random access property) on the flatbuf blob directly.
   a. There are no memory allocations at all so 1a overhead is completely removed. You can remove some of the overhead of 1a in Thrift by skipping over fields. Even if you skip fields you are still touching a lot of the bytes while "walking" the thrift representation so the operation is still O(N) to the bytes of the Thrift representation. We have tried that in the past and it didn't sufficiently solve the extreme cases.
   b. Flatbuf has a verification pass which will touch all the offsets to verify they are within bounds (this makes it O(N)). The verification pass is optional and for managed tables we can elide it by assuming the writer is not malicious. Without the verification pass there is no O(N) operation for flatbuf "parsing" at all.

[alamb]

Thank you @alkis.

I don't think anyone doubts the theoretical benefits of flatbuffer over thrift. What I am far more interested in is the actual practical ability to make footer parsing faster.

It has always been my belief the current thrift based parsers could be made significantly faster, which is exactly what we are now doing and I hope to have some numbers to share shortly

[alkis]

How do you plan to solve 1a? How noticeable is it in Rust?

[alamb]

How do you plan to solve 1a? How noticeable is it in Rust?

Initially by being smarter about not allocating structs we don't need

For for example, if you have 1000 columns with statistics, but your query is reading on 10 columns, or doesn't have predicates, (allocating and parsing) structures for statistics is wasteful. A custom thrift decoder makes it easier to avoid doing this

Depending on how far that gets us, we can also use more efficient string representations if needed (e.g. ptr + offset + length, rather than individual allocations)

[etseidl]

Thanks @alkis, all good points. If we were designing a system from the ground up I'd be on the flatbuffer bandwagon for sure.

How do you plan to solve 1a? How noticeable is it in Rust?

It is an issue for sure, but given our current processing pipeline it's unavoidable. We still (for the most part) take the thrift structures and turn them into crate specific structures. I'm able to be smart about transferring ownership of some structures so they are only allocated once, and I also do a good bit of slicing (rust equivalent of pointers) while reading so again strings/binary are only allocated once. But even if we kept the footer in memory and never reallocated binary data, vectors would still be an issue.

Even if you skip fields you are still touching a lot of the bytes while "walking" the thrift representation so the operation is still O(N) to the bytes of the Thrift representation

True, varints in particular are a pain.

At the end of the day, what this all boils down to is to realize the benefits of flatbuffers we would have to touch virtually every use of metadata in our reader as well as downstream consumers of it. That's going to be a very heavy lift and would need to come with some pretty significant benefits to be deemed worth the pain. I remember at the start of the V3 discussions someone saying Parquet doesn't have to be the best, it just has to be good enough to keep people from switching to something else. Here we're exploring the "good enough" path.

[alkis]

I remember at the start of the V3 discussions someone saying Parquet doesn't have to be the best, it just has to be good enough to keep people from switching to something else. Here we're exploring the "good enough" path.

Absolutely (that was be me btw).

At the end of the day, what this all boils down to is to realize the benefits of flatbuffers we would have to touch virtually every use of metadata in our reader as well as downstream consumers of it.

This is why the prototype for flatbufs and our shadow analysis in the fleet compares Thrift vs flatbufs + transform to Thrift's FileMetadata object and not vs raw flatbuf. This brings the bar of adoption very low. We encode flatbuf but read out a Thrift object as if we decoded Thrift. This is still 10x faster at the p999. For virtually all engines this can be plugged in with very little effort. Then if one wants the absolute best performance they can go ahead and remove the flatbuf to Thrift translation to realize the full benefit.

[alamb]

I am working on a benchmark binary here: https://github.com/alamb/parquet_footer_parsing