NVIDIA / NVIDIA/cudf

[FEA] Improve ORC reader filtering and performance

Open
#13,882 0 comments 0 reactions 0 assignees View on GitHub
0 - Backlog cuIO feature request libcudf Python
Dominant language
C++
Stars
9.8k
Forks
1.1k
Avg merge
3d 6m
Merged PRs (30d)
278

Description

### Background

libcudf includes readers and writers for two popular binary formats for columnar data: [Apache Parquet](https://en.wikipedia.org/wiki/Apache_Parquet) and [Apache ORC](https://en.wikipedia.org/wiki/Apache_ORC). These formats were originally introduced in 2013, and both have open source specifications ([ORC](https://orc.apache.org/specification/ORCv1/), [PQ](https://github.com/apache/parquet-format)) and reference implementations ([ORC](https://github.com/apache/orc), [PQ](https://github.com/apache/parquet-mr)) maintained by Apache. ORC also serves as the foundation for [Meta’s variant DWRF and their new format "Alpha"](https://www.cidrdb.org/cidr2023/papers/p77-chattopadhyay.pdf).

Both formats have hierarchical data layouts, support encoding and compression, include fully-featured type systems, and find widespread use in database systems and data warehousing. Please refer to [this paper](https://arxiv.org/pdf/2304.05028.pdf) by Zeng et al for a detailed comparison of the concepts, features and performance of Parquet and ORC binary formats. Please note that Parquet files are composed of “row groups” (~128 MB) and “pages” (~1 MB), and ORC files are composed of “stripes” (~70 MB) and “row groups” (10K rows).

Some of the differences include:
* finer granularity in data buffers by default in ORC (better for filtered IO and targeted lookups)
* finer granularity in bloom filters in ORC (supported at "row group" level in ORC, but not at the "page" level in Parquet)
* Dremel-encoding for list types in Parquet (faster decoding for >8 levels of nesting)
* support for [ACID transaction tables](https://orc.apache.org/docs/acid.html) in ORC datasets (enabling data updates without full re-write)
* In Parquet the data "page" is also the unit of encoding and compression, whereas in ORC each encoding "stream" and "compression chunk" often includes multiple "row groups".

### Expanding functionality of the ORC reader

The libcudf Parquet reader has gained functionality in key areas, including the chunked reader (release 22.12) to control how much of a table is materialized, and AST-based filtering (release 23.08) to avoid reading row groups that aren’t needed. Filtered IO (including bloom filters) is even more important to ORC users thanks to the fine granularity of ORC row groups (10k rows per row group). We should align our Parquet and ORC reader designs and separate shared utilities from format-specific details wherever possible.

| Topic | Status | Notes
|---|---|---|
| Add AST-based stripe filtering to the ORC reader | | #13348 added AST-based row group filtering to the Parquet reader. For this topic, we should accept an AST filter parameter, use it to determine matches stripes, read only those strips, and then post-filter the rows in the resulting table. We already have a `read_raw_orc_statistics` function to support these steps. We may refactor some of the AST + min/max stats tools to `utilities`. Also see issue #12512 |
| Add chunked reader for ORC | | See #12228 about this topic from Spark-RAPIDS. Chunked readers are useful because they allow for partial materialization of tables from their binary representation. #11867 added chunking for Parquet decoding, which means the compressed row groups were fully read and decompressed and then decoded up to a requested size in bytes. (tbd) is extending chunking to include Parquet decompression as well. Chunking helps libcudf applications avoid two limits: the [size_type](https://github.com/rapidsai/cudf/issues/13159) limit on row count and the GPU working memory limit for each worker |
| Support [bloom filters](https://en.wikipedia.org/wiki/Bloom_filter) in ORC reader | | See #4410. Due to ORC’s common usage for data lookup and filtered IO, supporting bloom filters in reads is especially important for ORC. This feature would allow the caller to specify equality conditions and check against ORC bloom filters. |
| Support index roundtripping in ORC | | See #8708, a request from cuDF-python to preserve the index when writing+reading a file |

### Performance optimizations for binary format reading

| Topic | Status | Notes
|---|---|---|
| Optimize ORC reader performance for list data | ✅ #13708 | We observed poor performance with singlely-nested lists and high row counts |
| Optimize ORC reader performance for decimal data | | See #13251, we need a parallel algorithm to replace the single-thread decoding of the variable-width encoded representation |
| Evaluate multi-kernel decoding in ORC | | See #13622 for experiments with multiple decode kernels, and #13302 for an example of a specialized strings decode kernel |
| Experiment with pipelining ORC reads | | See #13828 for information about reader pipelining |

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.