Add FlatBuffers footer to speed up metadata parsing

[alamb]

Describe the enhancement requested

@alkis is spearheading the improvement of Parquet footer metadata, with a proposal for adding an optional FlatBuffers based footer to the Parquet format. Andrew Bell noted on the mailing list there was no issue to track this, so filing one here

Quoting from the Proposal Document

Tabular data stored in Parquet files with thousands of leaf columns are becoming increasingly common, fueled by AI datasets. Decoding Parquet files always involves a two step process. First the Parquet metadata (aka footer) is fetched and resolved and then the row groups/column chunks are fetched and decoded. The two steps are serial because of the natural data dependency between them. Thus improving the time it takes to resolve Parquet metadata will allow engines to be more efficient to process Parquet files.

Related mailing list discussion: https://lists.apache.org/thread/j9qv5vyg0r4jk6tbm6sqthltly4oztd3

[abellgithub]

It could be that having Parquet files with thousands (one suggested millions) of columns is not a great use of the format. At some point a file format that solves everyone's problem doesn't solve anyone's problem well. I don't know if this is such a use case, but perhaps it deserves a philosophical discussion rather than a purely technical one.

[abellgithub]

I think that largest problem with the Thrift encoding of metadata is that you can't find anything -- you have to read all the data before locating the thing you want. It seems unfortunate to re-encode all the metadata in another format if you could find a way to provide offsets to things people need to find. It wouldn't need 100% direct access, but enough to allow people to locate things without decoding too much that they don't want. This could be done as some binary blob, which is essentially what you're proposing with flatbuf, but you could do something more simplistic than encoding all (most) of the data with flatbuf.

Also, having two sets of metadata in one file can lead to inconsistencies -- which data do you believe if things don't match?

[alamb]

if you could find a way to provide offsets to things people need to find.

I believe @etseidl has some ideas here

Also, Pierre Lacave says on https://lists.apache.org/thread/zxt7vx2bjmvng45nfwtm6gyj3c0w7wgb:

The approach we took is very similar to flatbuffer metadata + skiplist

Seeing this happening in parquet open interesting possibilities

This is explained in this blog:

Husky: Efficient compaction at Datadog scale | Datadog
https://www.datadoghq.com/blog/engineering/husky-storage-compaction/