Aisle: A fine pushdown parquet scanner
Today, we're excited to introduce Aisle, our high-performance Parquet file reader that implements
page-level predicate pushdown. This technological advancement significantly reduces I/O operations
and memory usage for analytical queries, especially for selective queries on large datasets.
Predicate Pushdown
Predicate pushdown is a query optimization technique used in database. It filters data in advance
to reduce the data passed to the parent node. The following figure describes how predicate pushdown works.
a > 30 AND b < 50
┌───────────────────────┐ ┌────────────────────────┐
│ ┏━━━━━┓┏━━━━━┓┏━━━━━┓ │ │ ┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐ │
│ ┃ 1 ┃┃ 9 ┃┃ 3 ┃ │ │ │ 1 ││ 9 ││ 3 │ │
│ ┗━━━━━┛┗━━━━━┛┗━━━━━┛ │ │ └ ─ ─ ┘└ ─ ─ ┘└ ─ ─ ┘ │
│ ┏━━━━━┓┏━━━━━┓┏━━━━━┓ │ │ ┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐ │
│ ┃ 20 ┃┃ 32 ┃┃ 24 ┃ │ │ │ 20 ││ 32 ││ 24 │ │
│ ┗━━━━━┛┗━━━━━┛┗━━━━━┛ │ │ └ ─ ─ ┘└ ─ ─ ┘└ ─ ─ ┘ │
│ ┏━━━━━┓┏━━━━━┓┏━━━━━┓ │━━━━━━▶ ┏━━━━━┓┏━━━━━┓┏━━━━━┓ │
│ ┃ 50 ┃┃ 47 ┃┃ 37 ┃ │ │ ┃ 50 ┃┃ 47 ┃┃ 37 ┃ │
│ ┗━━━━━┛┗━━━━━┛┗━━━━━┛ │ │ ┗━━━━━┛┗━━━━━┛┗━━━━━┛ │
│ ┏━━━━━┓┏━━━━━┓┏━━━━━┓ │ │ ┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐ │
│ ┃ 100 ┃┃ 99 ┃┃ 89 ┃ │ │ │ 100 ││ 99 ││ 89 │ │
│ ┗━━━━━┛┗━━━━━┛┗━━━━━┛ │ │ └ ─ ─ ┘└ ─ ─ ┘└ ─ ─ ┘ │
└───────────────────────┘ └────────────────────────┘
predicate pushdown
┌───────┐ ┌───────┐ ┌───────┐ ┌───────┐ ┌───────┐
│┏━━━━━┓│ │┌ ─ ─ ┐│ │ │ │ │ │ │
│┃ 1 ┃│ ││ 1 ││ │ │ │ │ │ │
│┗━━━━━┛│ │└ ─ ─ ┘│ │ │ │ │ │ │
│┏━━━━━┓│ │┌ ─ ─ ┐│ │ │ │ │ │ │
│┃ 20 ┃│ a > 30 ││ 20 ││ load b │ │ b < 50 │ │ load c │ │
│┗━━━━━┛│━━━━━━▶│└ ─ ─ ┘│━━━━━━▶│ │━━━━━━▶│ │━━━━━━▶│ │
│┏━━━━━┓│ │┏━━━━━┓│ │┏━━━━━┓│ │┏━━━━━┓│ │┏━━━━━┓│
│┃ 50 ┃│ │┃ 50 ┃│ │┃ 47 ┃│ │┃ 47 ┃│ │┃ 37 ┃│
│┗━━━━━┛│ │┗━━━━━┛│ │┗━━━━━┛│ │┗━━━━━┛│ │┗━━━━━┛│
│┏━━━━━┓│ │┏━━━━━┓│ │┏━━━━━┓│ │┌ ─ ─ ┐│ │ │
│┃ 100 ┃│ │┃ 100 ┃│ │┃ 99 ┃│ ││ 99 ││ │ │
│┗━━━━━┛│ │┗━━━━━┛│ │┗━━━━━┛│ │└ ─ ─ ┘│ │ │
└───────┘ └───────┘ └───────┘ └───────┘ └───────┘
- The upper one loads all rows and applies filter to each row. This approach may load too much unnecessary data.
- The lower one only loads columns that are included by predicates and then apply filters. After filtering, only load all data that matches. This approach greatly reduces I/O and improves performance and this is what Parquer has done for us.
Parquet uses predicate pushdown techniques to optimise query performance, but there are still a lot of things to do to get the best performance. Parquet provide RowSelection to determin which rows to be loaded and which rows not to be loaded. So we can get better performance if we can tell parquet reader not to load those rows that we don't want. But how do we know which rows should be selected before knowing the actual data?
As mentioned in the Querying Parquet with Millisecond Latency, we can use the statistics stored in the footer to skip data before loading the data. For example, If we know the max/min values of row groups, we can apply filters on the row groups and skip the whole row groups before loading them.
Fortunately, Parquet will write statistics(row group statistics, page index) in the Parquet metadata. By utilizing these statistics, we can skip unnecessary data more effectively without loading the actual data.
The following figure describes what we have done to implement an efficient parquet reader.
First, we load metadata from parquet file, and read the row group statistics. Row group statistics may contains max/min values of all column chunks in the row group. If we can get the max/min values successfully, then we can apply filters to them. As you can see, the row group 2 does not match our filters, so we can skip this row group.
After that, we read the page index in the row groups 1 and apply filters on them. Like row group statistics, page index alos contains max/min values for each page. So we can know which pages don't meet the filters and skip them.
Performance Results
Aisle's predicate filtering approach provides significant performance benefits, especially for selective queries on large datasets. We designed sets of benchmark scenarios to test the performance of Aisle. The result shows considerable improvement when using predicate pushdown compared to traditional approaches. Here is the result of reading 1.3GB parquet file with ordered data.
range query with ordered data
╔═══════════════════════════════════════════════════════════════════════════╗
parquet ╢███████████████████████████████████████████████████████████████████████████╟ 740.0068
Parquet + Page index ╢██████████████████████████████████████████████████████████████████████░░░░░╟ 691.7279
Aisle ╢███████████████████████████████░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░╟ 307.3197
Aisle + Page index ╢█████████████████████████████░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░╟ 287.6667
╠═══════════════════════════════════════════════════════════════════════════╣
0 740.0068
equivalent query with ordered data
╔═══════════════════════════════════════════════════════════════════════════╗
parquet ╢███████████████████████████████████████████████████████████████████████████╟ 652.1447
Parquet + Page index ╢██████████████████████████████████████████████████████████████████████░░░░░╟ 611.5472
Aisle ╢█░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░╟ 5.5786
Aisle + Page index ╢░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░╟ 2.717
╠═══════════════════════════════════════════════════════════════════════════╣
0 652.1447
(lower is better)
Please see here for more benchmark results.
Why Aisle
There are many projects that implement predicate pushdown, but they require closer integration with a query engine such as Datafusion. It is too complex to integrate but it is too redundant to implement by ourselves, too.
Aisle focuses on predicate pushdown and provides similar API to the ParquetRecordBatchStreamBuilder so that we can easily migrate and don't need to implement it by ourselves anymore.
When to Use Aisle
Aisle provides the most benefit in the following scenarios:
- Selective Queries: The more selective your predicates, the greater the benefit from Aisle.
- Sorted or Partially Sorted Data: When data has good locality within pages, page statistics become more effective.
- I/O-Constrained Environments: When I/O is your bottleneck, reducing the amount of data read provides substantial benefits.
- Large Parquet Files: The larger the files, the more important efficient filtering becomes.
Futures
While Aisle already provides significant benefits, we're continuing to improve it in several ways:
- Support for More Predicate Types: Currently, we support basic comparison operators (>, >=, <, <=). We are planning to add more operations and complex predicates.
- Multi-Column Predicates: Enhance support for predicates that involve multiple columns.
- Performance Optimizations: Continue refining our implementation for even better performance.