lance-format / lance-format/lance
parallelize zone statistics computation in scalar index training
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 7.1k
- Forks
- 852
- Avg merge
- 3d 18h
- Merged PRs (30d)
- 272
Description
Problem
ZoneTrainer::train computed every zone's statistics on a single task. chunk_concat_stream first copied the input stream into zone-sized batches, then one processor walked the zones sequentially, calling reset() between them. Zone statistics are independent of one another, so this pinned the whole computation to a single core regardless of machine size. The cost scales with per-zone work — a bloom filter has to hash every value into that zone's SBBF, which made it the dominant part of index build time.
Approach
Separate zone splitting from zone computation:
ZoneAssembler(serial) scans_rowaddrin a single pass and cuts at fragment boundaries and zone capacity, emitting each zone as zero-copyRecordBatchslices. This also removes thechunk_concat_streamcopy.process_zone(pure CPU) computes one zone's statistics and null row addresses, dispatched viaspawn_cpu.ZoneTrainer::newnow takes a processor factory instead of a single processor, so each zone gets its own processor.- Results are collected through
FuturesOrdered, with in-flight tasks capped atget_num_compute_intensive_cpus()for backpressure.
Zone order and contents are unchanged, so the on-disk index is byte-identical; no format change.
Results
Benchmarks added in this PR, comparing training performance only (default parameters). This is not an end-to-end measurement: it times builder.train(...) alone, excluding write_index and the dataset scan.
8M rows / 64 fragments:
| Benchmark | Before | After | Speedup |
|---|---|---|---|
bloomfilter_train_string (Utf8, 64 frags) |
395.5 ms | 15.5 ms | 25.5× |
zonemap_train_string (Utf8, 64 frags) |
65.9 ms | 11.3 ms | 5.8× |
zonemap_train (Int32, batch = 8192) |
30.2 ms | 9.15 ms | 3.3× |
The bloom filter gains the most, as expected: it has the largest per-zone workload (e SBBF), and the serial version spent nearly all of its time there.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by reading ZoneTrainer::train and ZoneTrainer::new, then trace how builder.train invokes scalar index training. Use the mentioned bloomfilter_train_string, zonemap_train_string, and zonemap_train benchmarks to compare training behavior. Done means zones are processed independently without changing their order or contents, and the on-disk index remains byte-identical.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- data-engineering, performance
- Issue type
- Refactor
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 52/100