Repository navigation
[C++][Parquet] Using BMI to implement filter pushdown #37559
Description
Describe the enhancement requested
From Selection Pushdown in Column Stores using Bit Manipulation Instructions, they said
We empirically evaluate the proposed techniques in the context of Apache Parquet using both micro-benchmarks and the TPC-H benchmark, and show that our techniques improve the query performance of Parquet by up to one order of magnitude with representative scan queries. Further experimentation using Apache Spark demonstrates speed improvements of up to 5.5X even for end-to-end queries involving complex joins.
And
We implemented Parquet-Select in C++, based on the open-source C++ version of the Arrow/Parquet library^1^ (version 8.0.0). For all operators that use BMI instructions, we implemented a dynamic dispatching mechanism to detect whether BMI support is available on the host processors at run time and fall back to an alternative implementation if BMI support is missing.
BMI was instroduced 10 years ago, so implementing this feature should have big benefits.
Component(s)
C++, Parquet
Activity
mapleFU commentedon Sep 5, 2023
When it goes to rep-def levels, I believe we already have some BMI2 impls:
arrow/cpp/src/parquet/level_conversion.cc
Line 128 in a526ba6
However, other decode part missing this.
Besides, currently, the Arrow Parquet implemention even don't implement the Predicate pushdown in C++. Acero has some
SelectionVector, but it doesn't use that.Maybe we can evaluate and implement that step by step, like Velox 🤔?
baibaichen commentedon Sep 5, 2023
I am currently working on gluten and clickhouse backend. Our team try to implement a filter push down like velox but using clickhouse expression evaluate framework which is not good since we have to build full
Columnbefore filter operation.The paper gives right direction, and I think we should implement filter push donw like this in apache arrow.
Would we have a meeting on this?
mapleFU commentedon Sep 5, 2023
What kind of interface does ClickHouse using around Parquet? I guess there are lots of work todo. first the expression should be cast to
arrow::Expression, and then we need support some lazy evaluation / filter reorder by selector or a row-range based on thearrow::Expression.Technically, the way like arrow-rs might be followed. As for BMI itself, I guess it's better an optional optimization rather than a neccessary-opt (like decode rep-deps and unpack in current parquet implemention)
baibaichen commentedon Sep 5, 2023
Agreed!
see ArrowBlockInputFormat , clickhouse use
RecordBatchFileReaderWe lack knowledge of how to build an expression evaluate framework based on arrow. It would be great that the arrow community could do this.
By the way, we also find that memmory copy hurt performanace, is it possible to directly decode into Clickhouse's data structure? The current code path looks like this :
see ArrowColumnToCHColumn
mapleFU commentedon Sep 5, 2023
Hmmm If ClickHouse support non-owned Buffer, or other, it could be simpler 🤔 Otherwise you need to implement the logic under
cpp/src/parquet/arrow... I guess thats really huge work todo(it will be easy at first, but finally you will need to write wrapper for every types, timestamp, decimal..). Though memcpy performance for binary type might be pool now, I guess it would be benefits when StringView and other is introduced.baibaichen commentedon Sep 5, 2023
Yes! that's why filter push down is important, which colud reduce memory copy significantly.
mapleFU commentedon Sep 6, 2023
Another thing is that have you do the field pruning and RowGroup statistics pruning? This could be done easily
mapleFU commentedon Sep 6, 2023
Maybe you can email me and @wgtmac . And when we have some RFC maybe we can deliver it in arrow weekly meeting?
[-][C++][Parquet]: Using BMI to implement filter pushdonw[/-][+][C++][Parquet] Using BMI to implement filter pushdonw[/+]baibaichen commentedon Sep 6, 2023
Cool!
@mapleFU @wgtmac let me know what's your timezone, so I can schedule a meeting.
[-][C++][Parquet] Using BMI to implement filter pushdonw[/-][+][C++][Parquet] Using BMI to implement filter pushdown[/+]mapleFU commentedon Sep 6, 2023
We're at UTC-8 now. We can chat these in mail since github issue is public, and it might not directly related to the issue?
31 remaining items
wgtmac commentedon Nov 27, 2023
Finally I have got some time to complete the design doc drafted by @mapleFU: https://docs.google.com/document/d/1SeVcYudu6uD9rb9zRAnlLGgdauutaNZlAaS0gVzjkgM/.
The proposal mainly is based on the discussion with @baibaichen @binmahone.
I think it would be good to get a consensus from the community before getting hands dirty on the implementation. Please take a look and any feedback are welcome! @emkornfield @fatemehp @pitrou @westonpace
pitrou commentedon Nov 27, 2023
This proposes a number of reader APIs based on row ranges, but never says how row ranges are computed in the first place?
emkornfield commentedon Nov 28, 2023
@pitrou I think the intent is that it is specifically abstract. I think there are a few different methods to produce the ranges:
@wgtmac I think this is partially covered in the design but it would be good to maybe make this more explicit
wgtmac commentedon Nov 28, 2023
I agree with @emkornfield that there are many approaches to produce row ranges.
AFAIK, many downstream projects have different expression APIs and only use the arrow layer of parquet-cpp (not the dataset layer). It is difficult to determine a single approach of producing row ranges for all downstream projects, but it is easy to make the agreement to push down row ranges to the parquet reader to achieve filtering. Therefore I leave the freedom of different engines to design their own logic to produce row ranges.
At the moment, I have marked filtering support of parquet dataset reader as a non-goal in the doc. My idea is to use expressions from Arrow compute to do something similar to what parquet-mr does: https://github.com/apache/parquet-mr/blob/master/parquet-column/src/main/java/org/apache/parquet/internal/filter2/columnindex/ColumnIndexFilter.java#L65-L104.
fatemehp commentedon Dec 1, 2023
Why is it necessary to have a RowRanges API? The ::parquet::internal::RecordReader has ReadRecords and SkipRecords APIs, this should be sufficient to read/skip ranges of rows.
This will reduce the burden of converting whatever upstream format of row ranges to the one compatible with what we define here.
P.S. We have considered removing the RecordReader from the internal scope:
#37003 (comment)
wgtmac commentedon Dec 1, 2023
IMO, it would be too late to optimize I/O and decoding when SkipRecords is called. Pushing down row ranges has good separation and makes it easy to do the planning before reading.
fatemehp commentedon Dec 1, 2023
I added a comment to the doc, I think we should think more about the format of the ranges both in terms of memory and performance.
I would consider analyzing the following options before making a decision:
A set of runs of 0s and 1s. These could be storage optimized/encoded and cheaply read.
Storing num_to_read/num_to_skip instead of from/to. If we limit the size of the runs, we could store them in uint16_t instead of the proposed int64_t for from/to.
A storage-optimized bitmap such as a RoaringBitmap.
emkornfield commentedon Dec 1, 2023
@fatemehp I think we are all ok with this, it is just waiting a PR: #37003 (comment)
wordhardqi commentedon Jan 4, 2024
do we have a PR for BMI now
mapleFU commentedon Jan 4, 2024
@wordhardqi Not yet, we should first planning a interface for high level pruning, and the work is on-going now
However, if you're interesting in BMI implemention, implement better
DecodeSpacedwould help the latter implementation.pitrou commentedon Jan 4, 2024
Please, stop obsessing over BMI or other "magical" optimization methods (which SIMD instructions are often viewed as). The correct way to reason about this should be 1) find bottlenecks 2) find portable methods to optimize them 3) only as a last resort, consider SIMD optimizations.
felipecrv commentedon Mar 2, 2024
There is a lot in the
FilterandTakeimplementations that can be improved even before we have the code structured in a way that can benefit from SIMD speed-ups. I'm marking myself as "Participating" on this discussion so I remember to announce the extraction of primitives that can be useful here.thisisnic commentedon Feb 18, 2026
This issue has been marked as stale because it has had no activity in the past 2 years. Please remove the stale label or comment below, or this issue will be closed in 14 days.