[EPIC] A collection of items to improve CASE performance

[alamb]

Is your feature request related to a problem or challenge?

@pepijnve and @chenkovsky has been working on a series of improvements to improve the performance of evaluating CASE expressions performance that I think should be highlighted / made more visible, so I am making a ticket to collect the work

TLDR

SELECT CASE WHEN ... ELSE ... END ...

Will go faster 🚀

Items

• Improve performance of queries of the form SELECT *, CASE ... END #18056
• Implement lazy evaluation for nvl #17982
• fix: lazy evaluation for coalesce #17357
• Short circuit complex case evaluation modes as soon as possible #17898
• #17972 Restore case expr/expr optimisation while ensuring lazy evaluation #17973
• Implement lazy evaluation for nvl2 #17983
• #17982 Make nvl a thin wrapper for coalesce #17991
• Optimize merging of partial case expression results #18152
• perf: Simplify CASE for any WHEN TRUE #17602
• Regression: error planning TPC-DS query: input schema nullability mismatch #17801
• perf: optimize CASE WHEN lookup table (2.5-22.5 times faster) #18183

[pepijnve]

Copying this over from an arrow-rs discord discussion.

Perhaps we can implement case when more efficiently using interleave. The current implementation strategy builds up a result one branch at a time as in this diagram (I made some mistakes in the labels, but I think the idea is clear enough).

Diagram

What if instead of merging after every branch we keep the partial results separate and instead update an index Vec<(usize,usize)> as we go. To be able to do that efficiently, we augment the record batch with a "row number" array that gets filtered along with the record batch itself. That gives us the offsets in the index vec to update. When evaluation is complete everything gets bundled up into the final result array with a single interleave operation.

Diagram

[rluvaton]

I improved zip in arrow for scalars by a lot:

• perf: add optimized zip implementation for scalars arrow-rs#8653

Currently waiting on review for the dependent PRs

• perf: add repeat_slice_n_times to MutableBuffer arrow-rs#8658
• perf: add optimized function to create offset with same length arrow-rs#8656

[rluvaton]

Added another massive case when improvement when the pattern is map like (when "aa" then 1 ...)

PRs:

• bench: create benchmark for lookup table like CASE WHEN #18203 - benchmark
• perf: optimize CASE WHEN lookup table (2.5-22.5 times faster) #18183 - perf improvement

it is 99% faster which means that you won't even notice that there is case when 😄

[pepijnve]

@alamb could you add #18152 to the description list please?