What causes "HyperLogLog: Invalid bucket index" in risingwavelabs/risingwave?

Fix rank derivation so it yields 1..=64: `((hash.leading_zeros() as u8) + 1).min(64)`

HyperLogLog: Invalid bucket index

Error message

HyperLogLog: Invalid bucket index

What it means

`UpdatableBucket::get_bucket` validates the rank index before reading from either the dense counter array or the sparse counter map. Valid ranks are 1..=64 (u64 registers); index 0 or >64 would index out of bounds or read nonexistent sparse entries, so it's rejected as an invariant violation.

Source

Thrown at src/expr/impl/src/aggregate/approx_count_distinct/updatable.rs:99

    }
}

impl EstimateSize for SparseCount {
    fn estimated_heap_size(&self) -> usize {
        self.inner.capacity() * std::mem::size_of::<(u8, u64)>()
    }
}

#[derive(Clone, Debug, EstimateSize, PartialEq, Eq)]
pub(super) struct UpdatableBucket<const DENSE_BITS: usize = 16> {
    dense_counts: [u64; DENSE_BITS],
    sparse_counts: SparseCount,
}

impl<const DENSE_BITS: usize> UpdatableBucket<DENSE_BITS> {
    fn get_bucket(&self, index: u8) -> Result<u64> {
        if index > 64 || index == 0 {
            bail!("HyperLogLog: Invalid bucket index");
        }

        if index > DENSE_BITS as u8 {
            Ok(self.sparse_counts.get(index))
        } else {
            Ok(self.dense_counts[index as usize - 1])
        }
    }
}

impl<const DENSE_BITS: usize> Default for UpdatableBucket<DENSE_BITS> {
    fn default() -> Self {
        Self {
            dense_counts: [0u64; DENSE_BITS],
            sparse_counts: SparseCount::new(),
        }
    }
}

View on GitHub (pinned to 6469eb736d)

Solutions

Fix rank derivation so it yields 1..=64: `((hash.leading_zeros() as u8) + 1).min(64)`
Confirm the hash produces 64-bit values consistent with HLL parameters
Rebuild aggregation state if serialized with different DENSE_BITS

Example fix

// before
let index = (value.leading_zeros()) as u8; // may be 0
// after
let index = ((value.leading_zeros() as u8) + 1).min(64);

Defensive patterns

Strategy: validation

Validate before calling

fn valid_rank(index: u8) -> bool { (1..=64).contains(&index) }

Type guard

fn in_range(index: u8) -> bool { index != 0 && index <= 64 }

Try / catch

match bucket.update(index, retract) {
    Err(e) if e.to_string().contains("Invalid bucket index") => return Err(anyhow!("HLL rank {} out of 1..=64", index)),
    other => other,
}

Prevention

Clamp computed ranks to 1..=64 before update
Ensure hash width matches DENSE_BITS configuration
Test rank generation over representative hash inputs

When it happens

Trigger: `UpdatableBucket::update` (or get/put paths) invoked with `index == 0` or `index > 64`, meaning the rank computed from the hash is outside the representable range.

Common situations: Modified or inconsistent rank computation (`leading_zeros` not offset/capped); deserialized state from an incompatible register width (DENSE_BITS mismatch).

Understand the failure class

Background: "value must be between 0 and 1" / "out of range" / "must not be negative" errors: fixing range-validation failures across open-source libraries — this error's family across 42 libraries.

Related errors

AI-assisted analysis of risingwavelabs/risingwave@6469eb736d (2026-09-11). Data as JSON: /api/errors/73fcc262714c8ca2. Report an issue: GitHub.