Consider removing `skip` from `RowSelector`

[Dandandan]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.

Currently RowSelector contains a pub skip: bool which means that the rows in the row selector needs to be skipped or not.
However, this field is not very useful as an optimal representation of a RowSelector will always be alternating selected and skipped rows.

I think we should consider dropping the skip field in order to simplify the api (and speed up / reduce memory overhead (from 16 to 8 bytes per element) as well).

We can represent a RowSelector as array of alternating select / skip / select rows.

e.g. :
[0, 10, 5, 10, 5] => select 0, skip 10, select 5, skip 10, select 5

Describe the solution you'd like

Drop the skip field, update implementation to take care of the new representation (select / skip based on alternation rather than via the field, (even/odd)).

Describe alternatives you've considered

Other representation, e.g. Vec<Range<..>>

Additional context

[alamb]

If we are going to change how RowSelector is implemented I think we should also include a veriant that allows for a Bitmap representation too (to handle the case where the selections are not very large). I promise to write this up as a ticket tomorrow

Related ticket:

• [Parquet] Add BooleanArray based row selection #6624

[alamb]

I filed an epic that tries to explain the overall goal

• [EPIC] Faster performance for parquet predicate evaluation for non selective filters #7456

Here is a related ticket where @tustvold describes some other ideas to improve RowSelections:

• Adaptive Parquet Predicate Pushdown Evaluation #5523

[Dandandan]

Thanks for connecting the issues!
The BooleanBuffer approach is more efficient for dense / non-selective filters, so would be great to have this as well.

Motivating this issue to remove skip is it will half the size of RowSelector from 16 bytes (for 64-bit CPU) to 8 bytes (so it might help in cases where it already is relatively dense / contains many selectors.

[alamb]

Like always, @XiangpengHao was ahead of us, and he also mentioned the size of the RowSelector in #7363 (comment)

[alamb]

BTW there is already a row-selector benchmark:

https://github.com/apache/arrow-rs/blob/a2cc42639b4ad5579d052e6f2317a413e2407e0f/parquet/benches/row_selector.rs#L1-L0

[XiangpengHao]

We can represent a RowSelector as array of alternating select / skip / select rows.

e.g. : [0, 10, 5, 10, 5] => select 0, skip 10, select 5, skip 10, select 5

But this makes concatenating/slicing selectors tricker, and can not accept row selectors that have two consecutive select/skip.

I'll prefer using a sentinel value to represent skip/select.

[alamb]

Another potential option might be an enum like this:

enum RowSelector {
  Skip(usize),
  Scan(usize),
  Bitmap(BooleanBuffer),
}
``

[Dandandan]

Concatenating/slicing selectors tricker

It seems just adding "0" on odd elements to denote "select 0" gives the same meaning?
Currently the output of most calls seems to be alternating skip/select anyway? So the main change seems to be that we always start with one of the two (e.g select) and go on from there.

Can not accept row selectors that have two consecutive select/skip.

Skip (5), Skip(5) is identical to Skip(10), so what would be the benefit from having consecutive select/skip?

Another potential option might be an enum like this:

enum RowSelector {
   Skip(usize),
   Scan(usize),
   Bitmap(BooleanBuffer),
}

Downside is that it is also 16 bytes per element instead of 8.

[Dandandan]

The nice thing is selectors: Vec<RowSelector> is private so it's possible to change it to Vec<usize> and keep the API backwards compatible.