Skip to content

Speed up merge and zip with a scalar side #11437

Description

@mightsleep

Is your feature request related to a problem or challenge?

DataFusion evaluates CASE WHEN c THEN expr ELSE literal END with kernels::merge, the scalar on one side. merge extends MutableArrayData once per row for the scalar side (try_extend(i, 0, 1) in arrow-select/src/merge.rs), about 6 ns per row.

Describe the solution you'd like

With a scalar side, merge is the transpose of filter: fill the output with the scalar and write the array side to the mask's set bits (set_indices). The validity has closed forms: no null buffer when neither side has nulls, the mask itself for a NULL scalar, otherwise (scalar valid ? !mask : 0) | expand(array validity, mask) in the same loop. Utf8View works the same way on the views, sharing the array's buffers. DataFusion's own scatter (physical-expr-common/src/utils.rs) already does this for a CASE without ELSE.

Prototype numbers:

  • kernel, TPC-H SF1 CASE inputs (Q14, Q8, Decimal128): 6 ns to 0.2 ns per row
  • DataFusion main, 10M ClickBench rows, one thread: SUM(CASE WHEN "IsMobile" = 1 THEN "ResolutionWidth" ELSE 0 END) 90 ms to 42 ms, COUNT(DISTINCT CASE ... ELSE 'desktop' END) 114 ms to 58 ms
  • dense masks with long runs gain little; there the existing run copy stays

Plan, one PR each, stacked:

  • bench(arrow): merge with a scalar side over run masks, a NULL scalar and decimals #11527 benchmarks for merge with a scalar side (literal and NULL scalar, random and run-shaped masks, i32 and Decimal128); Boolean and Utf8View benchmarks come with their PRs
  • primitive types and decimals (a scatter of T::Native), and Boolean (bitwise: expand(array bits, mask) | (scalar ? !mask : 0))
  • Utf8View and BinaryView (the same scatter on the views, the array's buffers shared)
  • Utf8, LargeUtf8, Binary (offsets in closed form; with ELSE '' the output bytes are the array's own buffer)
  • merge_n (@Abhisheklearn12)

zip with a scalar side has the same per-row MutableArrayData cost (6 to 7 ns a row), and merge(c, filter(y, c), s) is zip(c, y, s), so DataFusion can zip the full column for an infallible THEN instead of filter + merge:

Describe alternatives you've considered

Interleave with running counters, as zip does since #10368: about 2.6 ns per row and slower than today on long runs.

Additional context

No response

Activity

  1. Abhisheklearn12 commented on Oct 12, 2026

    @Abhisheklearn12
    Contributor

    take

  2. mightsleep commented on Oct 12, 2026

    @mightsleep
    ContributorAuthor

    Yes hello @Abhisheklearn12 thanks for the interest. I opened this one with the plan and prototypes above and I'm working through the stacked PRs (benchmarks are up in #11527, then primitives and decimals, Boolean, Utf8View and Utf8) rn, so I'd like to keep those. merge_n isn't designed yet and would be a good separate piece if you'd like to take it. Would that work for you?

  3. Abhisheklearn12 commented on Oct 13, 2026

    @Abhisheklearn12
    Contributor

    Yes hello @Abhisheklearn12 thanks for the interest. I opened this one with the plan and prototypes above and I'm working through the stacked PRs (benchmarks are up in #11527, then primitives and decimals, Boolean, Utf8View and Utf8) rn, so I'd like to keep those. merge_n isn't designed yet and would be a good separate piece if you'd like to take it. Would that work for you?

    Thanks @mightsleep, that works for me! Very sorry, I didn't see you were already working through the stack. I'll leave those to you. I'll take merge_n, before writing code, I'll put together a quick benchmark to see how much there is to gain when some inputs are literals, and post that here along with a rough design. I'll build on your scatter changes once they're up.

  4. mightsleep commented on Oct 14, 2026

    @mightsleep
    ContributorAuthor

    Adding zip with a scalar side to the plan: same per-row MutableArrayData cost (6 to 7 ns a row), and DataFusion could zip the full column for an infallible THEN instead of filter + merge. PR inc

  5. changed the title [-]Speed up merge with a scalar side[/-] [+]Speed up merge and zip with a scalar side[/+] on Oct 23, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Labels

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions