Build time regression for BITMAP and BTREE index

[wjones127]

It seems we got slower at building these indices around January 1, 2026.

https://bencher.dev/perf/weston-lancedb?key=true&reports_per_page=4&branches_per_page=8&testbeds_per_page=8&benchmarks_per_page=8&plots_per_page=8&reports_page=1&branches_page=1&testbeds_page=1&benchmarks_page=4&plots_page=1&clear=true&tab=benchmarks&measures=2c54be52-0df5-49e9-ba36-4bc78fa0edcf&branches=f7b04560-8a34-4842-a7c6-089a8d72e724&heads=f7b04560-8a34-4842-a7c6-089a8d72e724&testbeds=eee246dd-6a86-436e-b59b-7936e7f78f7e&benchmarks=482f2e45-51b8-48e4-a8fb-9aad44c4ef47

[wjones127]

This is for python/ci_benchmarks/benchmarks/test_index_training.py::test_index_training[low-float-BITMAP-5M]

[wjones127]

There is a regression in BTREE index training time around the same time.

[westonpace]

The highlighted commit seems very suspect (3216350)

If we are allowing dictionary for floating point then we are probably calculating cardinality for floating point which can definitely slow down our write speed which could slow down these benchmarks. We probably need some file writer benchmarks.

[wjones127]

Regression Analysis

Root Cause

The regression was introduced in commit 3216350 "feat: add dictionary encoding for 64bit types like int64/double" (#5594).

This commit extended dictionary encoding from 128-bit types only to also include 64-bit types (float64, int64). The BITMAP index benchmark uses float64 with low cardinality (100 unique values), which now triggers dictionary encoding where it previously did not.

Benchmark Results

Testing with S3 storage (localstack) isolating just the create_scalar_index call:

Commit	Time	Change
d486fbc (before)	260ms	baseline
3216350 (after)	294ms	+13%

Potential cause

The main change in that commit that isn't specific to 2.2 is in statistics.rs:

Before: only compute cardinality for 128-bit values

  let cardidinality_array = if self.bits_per_value == 128 {
      Some(self.cardinality())
  } else {
      None
  };

After: compute cardinality for 64-bit AND 128-bit values

  let cardidinality_array = match self.bits_per_value {
      64 | 128 => Some(self.cardinality()),
      _ => None,
  };

The cardinality() function uses HyperLogLog and iterates through ALL values:

  for val in u64_slice {
      hll.insert(val);
  }

[wjones127]

FYI @Xuanwo it seems likely that #5594 caused a regression in writing 2.0 files, since we are now putting all 64-bit values through hyper log log.

[Xuanwo]

oh, I see. Let me take a look. It's now a blocker issue for our next upgrading, right?

[wjones127]

I don't think it's a big enough deal for us to block release on it, but I think we should fix it soon.