Or filter pushdown into zone maps #14313
Conversation
…h a zone map down
| FilterPropagateResult ZoneMapFilter::CheckStatistics(BaseStatistics &stats) { | ||
| if (child_filter->filter_type == TableFilterType::CONSTANT_COMPARISON) { | ||
| auto &const_compare = child_filter->Cast<ConstantFilter>(); | ||
| if (const_compare.constant.type().IsTemporal()) { |
There was a problem hiding this comment.
Is this required? Can we make this work for all types?
src/optimizer/filter_combiner.cpp
Outdated
| break; | ||
| } | ||
| auto const_filter = make_uniq<ConstantFilter>(comp.type, const_val->value); | ||
| zone_filter = make_uniq<ZoneMapFilter>(); |
There was a problem hiding this comment.
Instead of creating ZoneMapFilter(x) OR ZoneMapFilter(y), can we make the child of a ZoneMapFilter the OR expression - i.e. ZoneMapFilter(x OR y)? That should allow more efficient skipping.
|
|
||
| namespace duckdb { | ||
|
|
||
| ZoneMapFilter::ZoneMapFilter() : TableFilter(TableFilterType::ZONE_MAP) { |
There was a problem hiding this comment.
Let's rename the ZoneMapFilter to an OptionalFilter - indicating the true meaning of this type of filter, namely that the table scan is allowed to filter rows based on this criteria, but not required, as opposed to our other table filters that actually enforce that the rows must be removed for correctness.
|
|
||
| string ZoneMapFilter::ToString(const string &column_name) { | ||
| D_ASSERT(child_filter->filter_type == TableFilterType::CONSTANT_COMPARISON); | ||
| auto const_filter = child_filter->Cast<ConstantFilter>(); |
There was a problem hiding this comment.
Can we make this work for all table filters?
src/storage/table/column_segment.cpp
Outdated
| @@ -398,6 +398,10 @@ idx_t ColumnSegment::FilterSelection(SelectionVector &sel, Vector &vector, Unifi | |||
| SelectionVector result_sel(approved_tuple_count); | |||
| auto &conjunction_or = filter.Cast<ConjunctionOrFilter>(); | |||
| for (auto &child_filter : conjunction_or.child_filters) { | |||
| if (child_filter->filter_type == TableFilterType::ZONE_MAP) { | |||
| // conjunction OR of zone map is handed in row_group.cpp. | |||
| return scan_count; | |||
There was a problem hiding this comment.
This should not be required here
|
Thanks! Looks great. |
This PR will create a zone map table filter when a OR/IN filter on an integer column is present above a table scan.
When are OR/IN filters are pushed down?
If the column is an integer type column. Based on some benchmarks, the overhead of checking the min max for integer columns when the values are unordered or distinct values are sparse is very little compared to the benefit you get when they are ordered and/order the distinct values are dense.
See the following results. I test or filter pushdown on the following columsn
lineitem.I test on ordered column values and unordered column values.
I select just two values around the minimum + ~(rowgroup size) and the maximum - ~(row group size). This way at least two row groups are emitted from the scan. I query on tpch datasets at sf1, sf10, sf100. Notice that pushing down the OR filter on an unordered version of lineitem is only ~0.1 second slower than not pushing down. This comes from the min max checks. Inspecting the explain analyze by hand, the zone map filter lets in every row group on the higher scale factors
Foreign Key Data (lineitem.l_orderkey)
Execution times to find 2 values in the
lineitem.l_orderkeycolumn. This benchmark is included in the PR and was performed on a c6id.8xlarge (32 cores, 64 GB memory).select * from {lineitem_ordered/random_sfXXX} where l_orderkey in (99584, 5900006);Primary key data.(orders.o_orderkey)
Execution times to find 2 values in the
orders.o_orderkeycolumn. Here every o_orderkey is distinct. However, the two values selected mean that in the random order case, all values are propagated through to the FILTER.select * from {orders_ordered/random_sfXXX} where o_orderkey in (99584, 5900006);Future work:
TODO: Add more tests