Is your feature request related to a problem or challenge? Please describe what you are trying to do.
Follow up to #10141.
RowSelection::intersection and RowSelection::union have specialized fast paths when both sides share the same backing (bitwise ops for Mask+Mask, run merging for Selectors+Selectors). The mixed arms, however, eagerly convert the entire mask to RLE via mask_to_selectors() and then run the selector-based algorithm.
For a fragmented bitmap this is the worst case: an alternating 3M-row mask (~375 KB as a bitmap) expands to 3M RowSelectors (~48 MB) just to compute an intersection. A natural use case that hits this is an externally supplied fragmented bitmap composed with selector-backed page-index pruning — DataFusion's ParquetAccessPlan::scan_selection performs exactly this kind of intersection.
Originally reported by @hhhizzz in #10141 (comment)
Describe the solution you'd like
Options, roughly in order of preference:
- Convert the selector-backed side to a bitmap (selectors → mask is cheap and contiguous via
boolean_mask_from_selectors) and use the existing bitwise Mask+Mask path. When the pattern is fragmented enough to be mask-backed on one side, the result is likely best kept mask-backed anyway.
- Stream the mask's runs through
MaskRunIter into the selector-merge algorithms without materializing a Vec<RowSelector>.
Describe alternatives you've considered
Keeping the eager conversion but capping it with the auto-strategy heuristic — more complex and still O(runs) allocation in the fragmented case.
Additional context
Per review feedback on #10141, this should land with benchmark coverage, e.g. a mixed-backing intersection/union case in parquet/benches/row_selection_cursor.rs using a fragmented (alternating) mask against a coarse selector-backed selection (cargo bench -p parquet --bench row_selection_cursor).
Is your feature request related to a problem or challenge? Please describe what you are trying to do.
Follow up to #10141.
RowSelection::intersectionandRowSelection::unionhave specialized fast paths when both sides share the same backing (bitwise ops for Mask+Mask, run merging for Selectors+Selectors). The mixed arms, however, eagerly convert the entire mask to RLE viamask_to_selectors()and then run the selector-based algorithm.For a fragmented bitmap this is the worst case: an alternating 3M-row mask (~375 KB as a bitmap) expands to 3M
RowSelectors (~48 MB) just to compute an intersection. A natural use case that hits this is an externally supplied fragmented bitmap composed with selector-backed page-index pruning — DataFusion'sParquetAccessPlan::scan_selectionperforms exactly this kind ofintersection.Originally reported by @hhhizzz in #10141 (comment)
Describe the solution you'd like
Options, roughly in order of preference:
boolean_mask_from_selectors) and use the existing bitwise Mask+Mask path. When the pattern is fragmented enough to be mask-backed on one side, the result is likely best kept mask-backed anyway.MaskRunIterinto the selector-merge algorithms without materializing aVec<RowSelector>.Describe alternatives you've considered
Keeping the eager conversion but capping it with the auto-strategy heuristic — more complex and still O(runs) allocation in the fragmented case.
Additional context
Per review feedback on #10141, this should land with benchmark coverage, e.g. a mixed-backing
intersection/unioncase inparquet/benches/row_selection_cursor.rsusing a fragmented (alternating) mask against a coarse selector-backed selection (cargo bench -p parquet --bench row_selection_cursor).