Skip to content

Commit 70fa4d9

Browse files
committed
perf: find the nth valid row from the end for NTH_VALUE(expr, -n) IGNORE NULLS
Every frame with a validity buffer now takes the bitmap path, so a negative `n` enumerated the frame's valid rows from its start, even when the frame had no NULLs. Generalize `last_set_bit` to `nth_set_bit_from_end` and use it for both `LAST_VALUE` and `NTH_VALUE` with a negative `n`.
1 parent a717eb4 commit 70fa4d9

1 file changed

Lines changed: 29 additions & 24 deletions

File tree

‎datafusion/functions-window/src/nth_value.rs‎

Lines changed: 29 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -532,44 +532,46 @@ impl NthValueEvaluator {
532532
fn valid_index_with_nulls(&self, valid: &BooleanBuffer) -> Option<usize> {
533533
match self.state.kind {
534534
NthValueKind::First => valid.set_indices().next(),
535-
NthValueKind::Last => last_set_bit(valid),
535+
NthValueKind::Last => nth_set_bit_from_end(valid, 1),
536536
NthValueKind::Nth => {
537537
match self.n.cmp(&0) {
538538
Ordering::Greater => {
539539
// SQL indices are not 0-based.
540540
let index = (self.n as usize) - 1;
541541
valid.set_indices().nth(index)
542542
}
543-
Ordering::Less => {
544-
let reverse_index = (-self.n) as usize;
545-
let valid_indices_len = valid.count_set_bits();
546-
if reverse_index > valid_indices_len {
547-
return None;
548-
}
549-
valid.set_indices().nth(valid_indices_len - reverse_index)
550-
}
543+
Ordering::Less => nth_set_bit_from_end(valid, (-self.n) as usize),
551544
Ordering::Equal => None,
552545
}
553546
}
554547
}
555548
}
556549
}
557550

558-
/// Returns the index of the last set bit in `bits`, or `None` if no bit is set.
551+
/// Returns the index of the `n`th set bit from the end of `bits`, where `n = 1` is the last
552+
/// set bit, or `None` if fewer than `n` bits are set.
559553
///
560554
/// The bits are read a 64-bit word at a time from the end, so the cost grows with the distance
561-
/// from the end to the last set bit rather than with the length of `bits`. Enumerating the set
562-
/// bits from the start instead is quadratic for a frame that grows with every row.
563-
fn last_set_bit(bits: &BooleanBuffer) -> Option<usize> {
555+
/// from the end to that bit rather than with the length of `bits`. Enumerating the set bits
556+
/// from the start instead is quadratic for a frame that grows with every row.
557+
fn nth_set_bit_from_end(bits: &BooleanBuffer, n: usize) -> Option<usize> {
558+
debug_assert!(n > 0, "n is 1-based");
564559
let chunk = UnalignedBitChunk::new(bits.values(), bits.offset(), bits.len());
565560
// The words hold `lead_padding` unset bits before `bits` and `trailing_padding` after it.
566561
let mut word_start = chunk.lead_padding() + bits.len() + chunk.trailing_padding();
567-
for word in chunk.iter().rev() {
562+
let mut remaining = n;
563+
for mut word in chunk.iter().rev() {
568564
word_start -= 64;
569-
if word != 0 {
570-
let bit = 63 - word.leading_zeros() as usize;
571-
return Some(word_start + bit - chunk.lead_padding());
565+
let ones = word.count_ones() as usize;
566+
if ones < remaining {
567+
remaining -= ones;
568+
continue;
569+
}
570+
// Clear the `remaining - 1` highest set bits, leaving the one we want on top
571+
for _ in 1..remaining {
572+
word ^= 1 << word.ilog2();
572573
}
574+
return Some(word_start + word.ilog2() as usize - chunk.lead_padding());
573575
}
574576
None
575577
}
@@ -731,7 +733,7 @@ mod tests {
731733
}
732734

733735
#[test]
734-
fn last_set_bit_matches_a_scan_from_the_end() {
736+
fn nth_set_bit_from_end_matches_a_scan_from_the_end() {
735737
// The slices cover every bit offset within a word, byte-aligned and unaligned starts,
736738
// and lengths from empty to several words, which are the cases `UnalignedBitChunk`
737739
// splits into a prefix, aligned words and a suffix.
@@ -752,12 +754,15 @@ mod tests {
752754
for offset in 0..70 {
753755
for len in 0..=200 {
754756
let slice = bits.slice(offset, len);
755-
let expected = (0..len).rev().find(|&i| slice.value(i));
756-
assert_eq!(
757-
last_set_bit(&slice),
758-
expected,
759-
"offset {offset}, len {len}"
760-
);
757+
for n in [1, 2, 3, 63, 64, 65, 130] {
758+
let expected =
759+
(0..len).rev().filter(|&i| slice.value(i)).nth(n - 1);
760+
assert_eq!(
761+
nth_set_bit_from_end(&slice, n),
762+
expected,
763+
"offset {offset}, len {len}, n {n}"
764+
);
765+
}
761766
}
762767
}
763768
}

0 commit comments

Comments
 (0)