5 ms·

Embedding user-defined indexes in Apache Parquet

144 points by jasim 1y ago

jasim 1y ago
I think this post is a response to some new file format initiatives, based on the criticism that the Parquet file format is showing its age. One of the arguments is that there is no standardized way to extend Parquet with new kinds of metadata (like statistical summaries, HyperLogLog etc.) This post was written by the DataFusion folks, who have shown a clever way to do this without breaking backward compatibility with existing readers. They have inserted arbitrary data between footer and data pages, which other readers will ignore. But query engines like DataFusion can exploit it. They embed a new index to the .parquet file, and use that to improve query performance. In this specific instance, they add an index with all the distinct values of a column. Then they extend the DataFusion query engine to exploit that so that queries like `WHERE nation = 'Singapore'` can use that index to figure out whether the value exists in that .parquet file without having to scan the data pages (which is already optimized because there is a min-max filter to avoid scanning the entire dataset). Also in general this is a really good deep dive into columnar data storage.
- jjtheblunt 1y ago
  nice summary!
- dmvinson 1y ago
  What are the new file format initiatives you're referencing here? This solution seems clever overall, and finding a way to bolt on features of the latest-and-greatest new hotness without breaking backwards compatibility is a testament to the DataFusion team. Supporting legacy systems is crucial work, even if things need a ground-up rewrite periodically.
  - dkdcio 1y ago
    Lance (from LanceDB folks), Nimble (from Meta folks, formerly known as Alpha); I think there are a few others https://github.com/lancedb/lance https://github.com/lancedb/lance https://github.com/facebookincubator/nimble https://github.com/facebookincubator/nimble
    - kernelsanderz 1y ago
      I’ve been excited about lancedb and its ability to support vector indexes and efficient row level lookups. I wonder if this approach would work for their design goals and still allow broader backwards compatibility with the parquet ecosystem. Have been intrigued by Ducklake, and they’ve leaned into parquet. Perhaps this approach will allow more flexible indexing approaches with support for the broader parquet ecosystem which is significant.
  - MasterIdiot 1y ago
    Off the top of my head: - Vortex https://github.com/vortex-data/vortex https://github.com/vortex-data/vortex - Lance https://github.com/lancedb/lance https://github.com/lancedb/lance - Nimble https://github.com/facebookincubator/nimble https://github.com/facebookincubator/nimble There are also a bunch of ideas coming out of academia, but I don't know how many of them have a sustained effort behind them and not just a couple of papers
- lmeyerov 1y ago
  Yeah I'm happy to see this, we have been curious as part of figuring out cloud native storage extensions to GFQL (graph dataframe-native query lang), and my intuition was parquet was pluggable here... And this is the first I'm seeing a cogent writeup. Likewise, this means, afaict, it's likewise pretty straightforward to do novel indexing schemes within Iceberg as well just by reusing this. The other aspect I've been curious about is the happy path pluggable types for custom columns. This shows one way, but I'm unclear if same thing.
  - jasim 1y ago
    I'm not sure if this is what you're looking for, but there is a proposal in DataFusion to allow user defined types. https://github.com/apache/datafusion/issues/12644 https://github.com/apache/datafusion/issues/12644
    - lmeyerov 1y ago
      Thank you, looking forward to reading!
  - alamb 1y ago
    We are actively working on supporting extension types. The mechanism is likely to be using the Arrow extension type mechanism (a logical annotation on top of existing Arrow types https://arrow.apache.org/docs/format/Columnar.html#format-metadata-extension-types https://arrow.apache.org/docs/format/Columnar.html#format-me...) I expect this to be used to support Variant https://github.com/apache/datafusion/issues/16116 https://github.com/apache/datafusion/issues/16116 and geometry types (note I am an author)
- hodgesrm 1y ago
  One question that the article does not cover: compaction. Adding custom indexes means you have to have knowledge of the indexes to compact Parquet files, since you'll want to reindex each time compaction occurs. Otherwise the indexes will at best be discarded. At worst they would even be corrupted. So it looks as if adopting custom indexes mean you are adopting not just a particular engine for reading but also a particular engine for compaction. That in turn means you can't use generic mechanisms like the compaction mechanism in S3 table buckets. Am I missing something?
- deepsun 1y ago
  My main problem with Parquet format is that it depends on Facebook's Thrift (competitor to gRPC).
Nelkins 1y ago
Cool, but this is very specific to DataFusion, no? Is there any chance this would be standardized so other Parquet readers could leverage the same technique?
- gdubya 1y ago
  The technique can be applied by any engine, not just DataFusion. Each engine would have to know about the indexes in order to make use of them, but the fallback to parquet standard defaults means that the data is still readable by all.
  - aerzen 1y ago
    But does data fusion publish a specification of how this metadata can be read, along with a test suite for verifying implementations? Because if they don't, this cannot be reliably used by any other impl
    - jasim 1y ago
      Parquet files include a field called key_value_metadata in the FileMetadata structure; it sits in the footer of the file. See: https://github.com/apache/parquet-format/blob/master/src/main/thrift/parquet.thrift#L1267 https://github.com/apache/parquet-format/blob/master/src/mai... The technique described in the article, seems to use this key-value pair to store pointers to the additional metadata (in this case a distinct index) embedded in the file. Note that we can embed arbitrary binary data in the Parquet file between each data page. This is perfectly valid since all Parquet readers rely on the exact offsets to the data pages specified in the footer. This means that DataFusion does not need to specify how the metadata is interpreted. It is already well specified as part of the Parquet file format itself. DataFusion is an independent project -- it is a query execution engine for OLAP / columnar data, which can take in SQL statements, build query plan, optimize them, and execute. It is an embeddable runtime with numerous ways to extend it by the host program. Parquet is a file format supported by DataFusion because it is one of the most popular ways of storing data in a columnar way in object storages like S3. Note that the readers of Parquet need to be aware of any metadata to exploit it. But if not, nothing changes - as long as we're embedding only supplementary information like indices or bloom filters, a reader can still continue working with the columnar data in Parquet as it used to; it is just that it won't be able to take advantage of the additional metadata.
gregw2 1y ago
Note that there are "Puffin files" associated with Iceberg which have some overlap with this functionality: https://iceberg.apache.org/puffin-spec/#file-structure https://iceberg.apache.org/puffin-spec/#file-structure
- DonHopkins 1y ago
  Speaking of Puffin files, Apache Parquet always makes me think of this 1978 SNL intro with Bill Murray and SNL bass player Buddy Williams: https://snltranscripts.jt.org/77/77sparaquat.phtml https://snltranscripts.jt.org/77/77sparaquat.phtml

144 points by jasim 1y ago

I think this post is a response to some new file format initiatives, based on the criticism that the Parquet file format is showing its age. One of the arguments is that there is no standardized way to extend Parquet with new kinds of metadata (like statistical summaries, HyperLogLog etc.) This post was written by the DataFusion folks, who have shown a clever way to do this without breaking backward compatibility with existing readers. They have inserted arbitrary data between footer and data pages, which other readers will ignore. But query engines like DataFusion can exploit it. They embed a new index to the .parquet file, and use that to improve query performance. In this specific instance, they add an index with all the distinct values of a column. Then they extend the DataFusion query engine to exploit that so that queries like `WHERE nation = 'Singapore'` can use that index to figure out whether the value exists in that .parquet file without having to scan the data pages (which is already optimized because there is a min-max filter to avoid scanning the entire dataset). Also in general this is a really good deep dive into columnar data storage.

jjtheblunt 1y ago
nice summary!
dmvinson 1y ago
What are the new file format initiatives you're referencing here? This solution seems clever overall, and finding a way to bolt on features of the latest-and-greatest new hotness without breaking backwards compatibility is a testament to the DataFusion team. Supporting legacy systems is crucial work, even if things need a ground-up rewrite periodically.
- dkdcio 1y ago
  Lance (from LanceDB folks), Nimble (from Meta folks, formerly known as Alpha); I think there are a few others https://github.com/lancedb/lance https://github.com/lancedb/lance https://github.com/facebookincubator/nimble https://github.com/facebookincubator/nimble
  - kernelsanderz 1y ago
    I’ve been excited about lancedb and its ability to support vector indexes and efficient row level lookups. I wonder if this approach would work for their design goals and still allow broader backwards compatibility with the parquet ecosystem. Have been intrigued by Ducklake, and they’ve leaned into parquet. Perhaps this approach will allow more flexible indexing approaches with support for the broader parquet ecosystem which is significant.
- MasterIdiot 1y ago
  Off the top of my head: - Vortex https://github.com/vortex-data/vortex https://github.com/vortex-data/vortex - Lance https://github.com/lancedb/lance https://github.com/lancedb/lance - Nimble https://github.com/facebookincubator/nimble https://github.com/facebookincubator/nimble There are also a bunch of ideas coming out of academia, but I don't know how many of them have a sustained effort behind them and not just a couple of papers
lmeyerov 1y ago
Yeah I'm happy to see this, we have been curious as part of figuring out cloud native storage extensions to GFQL (graph dataframe-native query lang), and my intuition was parquet was pluggable here... And this is the first I'm seeing a cogent writeup. Likewise, this means, afaict, it's likewise pretty straightforward to do novel indexing schemes within Iceberg as well just by reusing this. The other aspect I've been curious about is the happy path pluggable types for custom columns. This shows one way, but I'm unclear if same thing.
- jasim 1y ago
  I'm not sure if this is what you're looking for, but there is a proposal in DataFusion to allow user defined types. https://github.com/apache/datafusion/issues/12644 https://github.com/apache/datafusion/issues/12644
  - lmeyerov 1y ago
    Thank you, looking forward to reading!
- alamb 1y ago
  We are actively working on supporting extension types. The mechanism is likely to be using the Arrow extension type mechanism (a logical annotation on top of existing Arrow types https://arrow.apache.org/docs/format/Columnar.html#format-metadata-extension-types https://arrow.apache.org/docs/format/Columnar.html#format-me...) I expect this to be used to support Variant https://github.com/apache/datafusion/issues/16116 https://github.com/apache/datafusion/issues/16116 and geometry types (note I am an author)
hodgesrm 1y ago
One question that the article does not cover: compaction. Adding custom indexes means you have to have knowledge of the indexes to compact Parquet files, since you'll want to reindex each time compaction occurs. Otherwise the indexes will at best be discarded. At worst they would even be corrupted. So it looks as if adopting custom indexes mean you are adopting not just a particular engine for reading but also a particular engine for compaction. That in turn means you can't use generic mechanisms like the compaction mechanism in S3 table buckets. Am I missing something?
deepsun 1y ago
My main problem with Parquet format is that it depends on Facebook's Thrift (competitor to gRPC).

Nelkins 1y ago

Cool, but this is very specific to DataFusion, no? Is there any chance this would be standardized so other Parquet readers could leverage the same technique?

gdubya 1y ago
The technique can be applied by any engine, not just DataFusion. Each engine would have to know about the indexes in order to make use of them, but the fallback to parquet standard defaults means that the data is still readable by all.
- aerzen 1y ago
  But does data fusion publish a specification of how this metadata can be read, along with a test suite for verifying implementations? Because if they don't, this cannot be reliably used by any other impl
  - jasim 1y ago
    Parquet files include a field called key_value_metadata in the FileMetadata structure; it sits in the footer of the file. See: https://github.com/apache/parquet-format/blob/master/src/main/thrift/parquet.thrift#L1267 https://github.com/apache/parquet-format/blob/master/src/mai... The technique described in the article, seems to use this key-value pair to store pointers to the additional metadata (in this case a distinct index) embedded in the file. Note that we can embed arbitrary binary data in the Parquet file between each data page. This is perfectly valid since all Parquet readers rely on the exact offsets to the data pages specified in the footer. This means that DataFusion does not need to specify how the metadata is interpreted. It is already well specified as part of the Parquet file format itself. DataFusion is an independent project -- it is a query execution engine for OLAP / columnar data, which can take in SQL statements, build query plan, optimize them, and execute. It is an embeddable runtime with numerous ways to extend it by the host program. Parquet is a file format supported by DataFusion because it is one of the most popular ways of storing data in a columnar way in object storages like S3. Note that the readers of Parquet need to be aware of any metadata to exploit it. But if not, nothing changes - as long as we're embedding only supplementary information like indices or bloom filters, a reader can still continue working with the columnar data in Parquet as it used to; it is just that it won't be able to take advantage of the additional metadata.

gregw2 1y ago

Note that there are "Puffin files" associated with Iceberg which have some overlap with this functionality: https://iceberg.apache.org/puffin-spec/#file-structure https://iceberg.apache.org/puffin-spec/#file-structure

DonHopkins 1y ago
Speaking of Puffin files, Apache Parquet always makes me think of this 1978 SNL intro with Bill Murray and SNL bass player Buddy Williams: https://snltranscripts.jt.org/77/77sparaquat.phtml https://snltranscripts.jt.org/77/77sparaquat.phtml