Potential Improved multiple column aggregation performance by using bitmasks rather than `Vec<bool>`

[alamb]

Is your feature request related to a problem or challenge?

@rluvaton notes on #17977:

once and if we change from &mut [bool] to mutable packed bits we could:

1. evaluate in chunks of 64 items (I tried different variations to see what is the best - you can tweak in the godbolt above with different type and size to check for yourself), 64 is not necessarily the best but it will be the fastest I think for doing AND with the equal_to_results boolean buffer
2. add optimization for nullable as well by just doing bitwise operation at 64 items at a time and avoid the cost of getting each bit manually
3. skip 64 items right away if the the equal_to_results equal to 0x00 (i.e. all false)

I believe he is referring to this code:

datafusion/datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs

Lines 71 to 86 in 73038f5

	/// The vectorized version equal to
	///
	/// When found nth row stored in this builder at `lhs_row`
	/// is equal to the row in `array` at `rhs_row`,
	/// it will record the `true` result at the corresponding
	/// position in `equal_to_results`.
	///
	/// And if found nth result in `equal_to_results` is already
	/// `false`, the check for nth row will be skipped.
	fn vectorized_equal_to(
	&self,
	lhs_rows: &[usize],
	array: &ArrayRef,
	rhs_rows: &[usize],
	equal_to_results: &mut [bool],
	);

Describe the solution you'd like

So basically rather than passing in &[mut bool] it would take a BooleanBufferBuilder or something equivalent.

    fn vectorized_equal_to(
        &self,
        lhs_rows: &[usize],
        array: &ArrayRef,
        rhs_rows: &[usize],
        equal_to_results: &BooleanBufferBuilder, // <--- Pass in some sort of bitmask representation rather than Vec<bool>
    );

Describe alternatives you've considered

No response

Additional context

No response

[rluvaton]

Yes, I was waiting for update for the arrow pr to be available in datafusion:

• feat: add apply_unary_op and apply_binary_op bitwise operations arrow-rs#8619

[alamb]

This will be released in arrow 57.1.0 -- I am hoping we can release it next week

[Omega359]

I got interested in this and did a bit of work for switching to BooleanBufferBuilder Omega359@71382a2 but given @rluvaton's PR in arrow-rs I'm not sure it's useful now.

Benchmarking with aggregate_vectorized showed no direct improvements from this.

[rluvaton]

This was the reason for my arrow rs pr

I'm waiting for it to get released so I could optimize this.

The code in your link work bit by bit from what I saw and it is not what I had in mind as this will actually be slower
Instead for primitives you would compare the entire array, and get a Boolean buffer which then you do bit manipulation to update the equals to

[Omega359]

The code in your link work bit by bit from what I saw and it is not what I had in mind as this will actually be slower Instead for primitives you would compare the entire array, and get a Boolean buffer which then you do bit manipulation to update the equals to

Right, yup. I was just doing a straight port just to see how much work it would be before refactoring. I'll leave it your capable hands :)